Фернан Гонсалес, желавший стать «творцом королей» и уже однажды потерпевший неудачу в этом качестве, поддерживал и направлял недовольство леонцев. В армии созрел заговор, и в один прекрасный день весной 858 года Санчо лишился своего королевства.

Пока свергнутый монарх добирался до Памплоны, резиденции его дяди Гарсии, Фернан Гонсалес и другие представители знати собрались, чтобы выбрать нового короля. Их выбор пал на Ордоньо IV. Он был сыном Альфонсо IV и, следовательно, кузеном Санчо. Но ничто, кроме происхождения, не могло обеспечить ему голоса выборщиков. Его деформированной фигуре (принц был горбат) соответствовал раздражительный, мрачный и злобный характер, так что впоследствии его всегда называли Ордоньо Злой. Тем не менее, поскольку, кроме него, не было ни одного взрослого члена королевской семьи, альтернативы не было. Граф Кастилии отдал ему в жены свою дочь Уракку, вдову Ордоньо III, которая, таким образом, стала королевой Леона вторично.

Пока шли выборы его преемника, Санчо в Памплоне рассказывал о своих несчастьях. Его бабушка, престарелая, но честолюбивая Феуда, которая до сих пор правила Наваррой от имени сына, хотя он уже давно достиг возраста, когда мог действовать самостоятельно, тепло поддержала Санчо и поклялась вернуть ему королевство любой ценой. Однако это было совсем не простое предприятие, поскольку у Санчо не было друзей в его утраченном королевстве, а Наварра, с другой стороны, была слишком слаба, чтобы в одиночку нападать на Леон и Кастилию. Поэтому Феуде нужен был союзник, причем сильный. Более того, чтобы Санчо сохранил свой трон, после того как он будет ему возвращен, было важно, чтобы он перестал быть всеобщим посмешищем из-за своей тучности. Его полнота не была наследственной. Она стала результатом какого-то нарушения, с которым должен был справиться хороший врач. Но такого можно было найти только в Кордове, где собралась вся научная и культурная элита. Одновременно Феуда верила, что в Кордове она сможет найти необходимого ей союзника. Короче говоря, она решила добыть у халифа врача, который вылечит ее внука, и армию, которая восстановит его на троне.

Разумеется, для ее гордости такой шаг был в высшей степени оскорбительным и унизительным. Ей не хотелось искать помощи у нечестивца, с которым она больше тридцати лет находилась в состоянии войны. Не проходило и года, чтобы он не совершал набеги на ее деревни, сжигая посевы и убивая жителей. Но ее любовь к внуку, желание увидеть его снова на троне и негодование из-за дурного с ним обращения подданных помогли ей преодолеть антипатию, и она отправила посольство в Кордову.