Наследником погибшего в бою Гарсии III стал его сын Санчо IV - 14-летнего подростка провозгласили "королем Нахеры" в военном лагере возле Атапуэрки. Пока он не достиг совершеннолетия, регентом была его мать Стефания де Фуа, но она умерла в 1058 году, и король стал править самостоятельно. Первым его делом стал союз с дядей Рамиро I Арагонским против эмира Сарагосы Абу Джафара Ахмада I ибн Сулеймана ал-Муктадира, которого наваррцы и арагонцы победили и обложили данью.

Тайфа (эмират) Сарагоса в ХI веке
Однако родственники в семье Санчо Великого продолжали оставаться гнидами - в 1067 году на Наварру напал король Санчо II Кастильский, сын Фернандо I и двоюродный брат Санчо IV. К тому времени Рамиро I уже умер, и правитель Наварры попросил помощи у его сына (и другого своего двоюродного брата) Санчо I Арагонского - так что конфликт кузенов получил наименование "Война трех Санчо". Победу удалось одержать кастильцам - у них было несправедливое преимущество в лице капитана Родриго (ака Руя) Диаса де Вивара (ака Бивара), который позже войдет в "фольклор народов" как Эль Сид Кампеадор. Наварра потеряла области Буребу, Альта-Риоху и Алаву.
Однако настоящая змея всегда греется на груди - в данном случае даже две змеи. 4 июня 1076 года во время охоты возле Пеньялены король Санчо IV был убит собственным братом - Рамон Гарсес столкнул его с обрыва, причем в заговоре была замешана и их сестра Эрмесинда. Убийцы тут же сбежали - Рамон (получивший прозвище Братоубийца) в Сарагосу, где умер в 1079 году, а Эрмесинда в Кастилию, где женилась и прожила до 1110 года. По месту своей смерти Санчо IV получил прозвище Пеньяленский.

Гробница короля Санчо II Кастильского в Бургосе
У убитого короля было двое маленьких сыновей, Гарсия и Рамон, но поскольку Санчо II Кастильский тут же вознамерился оккупировать Наварру, знать королевства призвала правителя Арагона и отдала корону ему - он стал королем Санчо V. Так Наварра на 60 лет попала под "арагонское иго" - вслед за Санчо V на престол всходили его потомки Педро I и Альфонсо I Воитель. Однако когда 7 сентября 1134 года Альфонсо I, потерпевший от сарацинов сокрушительное поражение у Фраги, умер, над землями гордого народа басков снова воссияло солнце свободы...
Лидером "реставрации" стал потомок побочной ветки династии Хименес - правправнук Санчо III Великого (сын Рамиро Санчеса, сына Санчо Гарсеса, внебрачного сына короля Гарсии III) Гарсия Рамирес. Героем он стал неспроста - по матери, Кристине Родригес, он был внуком того самого Сида Кампеадора (так что потомки Руя Диаса таки стали королями, да). Он жил в Кастилии, политэмигрантя, и когда узнал о поражении Альфонсо Воителя у Фраги, собрал небольшую армию и вторгся в Наварру. Жители встретили его с восторгом и провозгласили королем (и уже не Памплоны, и не Нахеры, а Наварры) Гарсией IV Восстановителем (Эль Рестаурадор).

Альфонсо VII Кастильский
Однако же времена величия Наварры прошли, и чтобы выжить, надо было пресмыкаться. Гарсия IV вынужден был признать себя "приемным сыном" нового правителя Арагона Рамиро II Монаха. Но это не понравилось Альфонсо VII Кастильскому, который в 1136 году отобрал у Наварры Ла-Риоху и заставил Гарсию IV принести вассальную клятву.
В 1137 году король Наварры попытался "скинуть иго", заключив союз с Афонсу I Португальским, но через три года вынужден был снова подчиниться Кастилии. Взамен, правда, удалось получить завоеванную кастильцами Сарагосу. В дальнейшем Восстановитель решил сохранить союз с Кастилией - в 1147 году он женился на Уракке, дочери Альфонсо VII, а в 1147 году помог тестю отвоевать Альмерию у мавров. Умер король Гарсия IV 21 ноября 1150 года.