El origen de este linaje se remonta al hijo del conde Ordoño de Gaviria, Galindo Ordoñes, el que "airado por el Rey de Navarra", su señor, según refiere Lope García Salazar, vino a establecerse en "Zamudio" y construyó el monasterio de Arteaga, casó con la hija de Martín Roys de Junquera, naciendo de esta unión Furtún Galíndes de Zamudio que casó con Mari Ortis, hija de Garci Tuerto de Basurto. De este matrimonio nació Ochoa Ortis de Zamudio, e Iñigo Ortis de Zamudio, y Ordoño de Zamudio. Mari Sanches casó con Ordoño de Guenes y Juana, que casó en Villela iniciando la descendencia de los Anucibay. El mayor de todos, Ochoa Ortis, heredó el solar de Arteaga Gaviria, el monasterio de Arteaga y estaba casado con Navarra, hija de Juan Lopes de Ganboa, el Viejo, de la que nacieron dos hijas, de las que una casaría con Sancho García de Murga, y otra con Garci Lopes de Salazar, en Estremeaña. Ordoño de Zamudio, el segundo hijo, se estableció en Olariaga de Zamudio, y al no tener su hermano mayor hijo varón, le correspondió en herencia San Martín de Zamudio de Arteaga, y sus hermanos lo consideraron como el mayor.
De su matrimonio con Teresa nació Ordoño de Zamudio que casó a su vez con Mencía, hija de Sancho Ferrandes de las Ribas. Heredaron Olariaga, San Martín de Arteaga por parte de su padre Ordoño, y las torres de Salcedo por su madre. El hijo mayor de Ordoño de Zamudio, Sancho Ortis, que heredó el solar de su padre se casó con la hija de Furtún García de Avendaño de la que tuvo a Juan Sánches de Zamudio que fue a establecerse en Berantevilla. Pero fue otro hijo, Ordoño de Zamudio, el que heredó el solar de los Zamudio, que heredó asimismo el solar de Lezama que le correspondió por su matrimonio con la hija de Pedro de Lezama. Muerta la mujer, casó con Mayor, hija de Martín Sánches de Legizamón, de la que nació Sancho Ortis, que heredó el solar de Zamudio. Este Sancho se casó con Juana, hija bastarda de Gomes Gonzáles de Butrón, naciendo de esta unión Ordoño, el que heredó el solar de Zamudio, y de esta generación surgieron los descendientes que prolongarían el linaje de los Zamudio.