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

После отъезда послов Наварры Абд-ер-Рахман послал за евреем Хасдаем, дал ему соответствующие инструкции и попросил отправиться в Наварру. Халиф не мог сделать лучший выбор. Хасдай обладал всеми качествами, необходимыми для выполнения такой миссии. Он свободно говорил на языке христиан, обладал медицинскими знаниями, одновременно был государственным деятелем. Все, кто когда-либо сталкивался с ним, высоко отзывались о его талантах, эрудиции и широчайших возможностях. Незадолго до этого посол из отдаленного уголка Германии заявил, что еще не встречал человека, столь сведущего в дипломатических премудростях.

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

Халифу очень хотелось повысить самооценку и одновременно порадовать своих людей невиданным зрелищем – христианская королева и два короля униженно молят его о помощи. Поэтому он особенно настаивал на выполнении этого условия, хотя и предвидел, что гордой Феуде оно придется не по нраву. Поездка в Кордову станет еще большим унижением для королевы, чем то, которому она уже себя подвергла, вступив в дружеские отношения с извечным врагом. Таким образом, достижение договоренности с Феудой стало самой тонкой и деликатной частью миссии Хасдая. Чтобы даже только сделать такое предложение, не говоря уже о том, чтобы получить согласие королевы, требовался исключительный такт и немалая ловкость. Но и тут еврей оправдал свою репутацию искуснейшего из людей. Высокомерная королева Наварры была покорена «очарованием его слов, житейской мудростью, непревзойденной изобретательностью и многочисленными хитроумными уловками» – так выразился современный еврейский поэт. Убедившись, что иного выхода нет и за восстановление внука на престоле придется заплатить столь высокую цену, она смирила гордыню и согласилась предпринять поездку в Кордову.

Испания увидела странное зрелище. Королева Наварры в сопровождении длинной вереницы знати и духовенства следовала короткими переходами в Кордову. С ней был Гарсия и несчастный Санчо, здоровье которого пока не слишком улучшилось, и передвигался он с помощью Хасдая. Это зрелище было приятно для глаз мусульман, но еще больше оно радовало евреев, которые знали, что оно организовано одним-единственным человеком, принадлежавшим к их вере. Поэты, соревнуясь друг с другом, наперебой велеречиво восхваляли возвращение Хасдая.