Fue mandada a construir a mediados del siglo XVI por Diego Martínez de Paternina y Samaniego y tiene reformas posteriores realizadas en los siglos XVII y XVIII. Es un enorme edificio con tres fachadas, resaltando en el ángulo de su fachada posterior un magnífico balcón esquinero y un cilindro que asemeja a la arquitectura castrense. Esta casa-palacio ostenta dos escudos, uno pequeño y renacentista, situado en la misma clave del arco del ingreso del siglo XVI y otro, más importante, barroco, colocado sobre él, en el frontal de la fachada, cuartelado con las armas de Paternina, Ruiz de Bergara, Samaniego y Ruiz de Gaceta. En esta casa fue donde pernoctó Napoleón en su estancia en Labastida.
Justo en frente de la Casa de los Paternina, en el número 1 6 de la Calle Mayor, se levanta otra espléndida casa palaciega exenta, la casa Palacio Garizábal.
Su fachada principal y las partes visibles de sus laterales están realizadas en piedra de sillería, habiendo sido recientemente rehabilitadas. En ella destacan los aleros de madera, los herrajes de los balcones y las curiosas formas geométricas realizadas en piedra. En el centro del último piso, entre los balcones, se encuentra otro magnífico escudo cuartelado. Es quizás el más rico y complicado, con su yelmo empenachado, leones rampantes y amplio lambrequín cuyas cuatro puntas terminan en bellas figuras humanas.
Destaca igualmente su portal ampuloso y con amplia escalinata. Organizaciones similares de patios y bodegas anexas o bajo la misma casa se repiten en numerosos edificios de la villa.