Los romanos, que estuvieron en todos los sitios, también estuvieron aquí. Y fortificaron el cerro con un perímetro defensivo que encerró la primera historia de Olite. Más tarde, los godos aprovecharon aquellas piedras y la población se empezó a sumergir en la Edad Media y sus guerras sin fin.
Sin embargo, Olite se las arregló para brillar y prosperar, y tanto prosperó que Carlos III el Noble, rey de Navarra, emprendió en la villa lo que acabaría siendo un proyecto colosal.
Comenzaba el siglo XV y Eriberri, que es el otro nombre de Olite, vivía su edad dorada con Carlos al mando. Un monarca singular, con gusto por los libros y las artes, escasa tendencia a batallar e interés en tender puentes y entablar relaciones amistosas con los reinos vecinos. El fiero guerrero medieval empezaba a dejar paso al sofisticado y cortesano príncipe renacentista, y el palacio de los Reyes de Navarra, promovido por Carlos III, iba a ser el exacto reflejo de esos cambios.