Начало дипломатической миссии оказалось удачным. Афанасий Нагой и его товарищ Фёдор Писемский добились согласия хана на заключение договора. После долгих переговоров был согласован текст «докончальной грамоты», на котором хан «принёс шерть» (дал клятву) в январе 1564 года. Однако договор надлежало утвердить на собрании крымской знати, среди которой было немало противников улучшения отношений с Москвой. Сам же хан Девлет-Гирей тянул время и выпрашивал у послов всё новые подарки, а литовские дипломаты сумели настроить против московитов влиятельных беев при ханском дворе. Нагой был согласен удовольствоваться не союзом, а миром, но крымская знать после «большой думы» стала требовать в обмен уступку Казани и Астрахани, на что Грозный не мог пойти из принципа. Стремительно портившиеся отношения привели к походу крымского войска в рязанские уезды и к аресту московского посольства. Нагой и члены его миссии, будучи в Крыму посажены в крепость Чуфут-Кале, всё же смогли установить связь с промосковски настроенными мурзами во главе с князем Сулешем и пытались изменить ситуацию. Из Москвы хану пообещали большие подарки («поминки»), и переговоры возобновились, но Девлет-Гирей колебался. «Государь де ваш не верит мне, а яз не верю государю вашему», — заявил он Нагому в июле 1566 года.
В итоге договор так и не был заключён, а послы сидели в Крыму в качестве почётных пленников. Афанасий Нагой и в этих условиях не терял времени — собирал информацию. От простых татар, русских «полоняников» и промосковски настроенной крымской знати ему стало известно о намерениях татар и турок, в том числе о планах поднять восстание черемисов (марийцев), недовольных русским владычеством в Поволжье, и о задуманном турецким султаном походе на Астрахань. Подробные сведения об этом последнем предприятии доставил послам захваченный в плен «сын боярский», царский посланник в Ногайскую орду Семён Мальцев. Ему довелось после продажи в рабство в Азове служить гребцом на турецкой галере, и одно время он был даже прикован цепью к пушке. Оказавшись в Бахчисарае, Мальцев сумел связаться с послами и не раз поставлял им ценную информацию.
Прошло несколько лет, прежде чем посольство было отпущено домой в обмен на задержанных в Москве крымских дипломатов. Только в ноябре 1573 года Нагой и Писемский вернулись в Москву. Иван Грозный высоко ценил их деятельность: в июне 1571 года послам было сообщено царской грамотой, что они заслужили жалованье «из опришнины». С тех пор карьера Нагого резко пошла вверх. Афанасий Фёдорович стал думным дворянином, дворовым воеводой, одним из ближайших советников царя по вопросам внешней политики и нередко участвовал в переговорах: в августе 1574 года принимал крымских гонцов, в декабре беседовал с членами датского посольства, в январе 1575-го встречался с имперскими гонцами, в марте — с литовскими, в июне — со шведскими, в июле — с датчанами, в январе 1576-го — с имперскими дипломатами, в октябре — с крымскими посланцами, в ноябре — с польскими. Обладая нужным опытом и способностями, он заменил во внешнеполитической сфере казнённого в 1570 году дьяка Ивана Михайловича Висковатого. Наиболее важным делом были переговоры с имперскими послами Яном Кобенцлем и Даниилом Принцем, где был в принципе согласован план раздела Речи Посполитой. Иван Грозный согласился с выдвижением кандидатуры австрийского эрцгерцога Эрнста на польский престол при условии включения Великого княжества Литовского в состав Русского государства. Платой за согласие императора должно было стать обещание Москвы выступить вместе с Веной против турок
{32}.Кроме того, уже к ноябрю 1576 года Нагой являлся козельским наместником, а затем брянским. Он в числе других гостей присутствовал на царской свадьбе с Анной Васильчиковой, а осенью 1578 года женил Ивана Грозного на своей племяннице Марии Нагой и стал одним из самых близких к царю людей. Лидерство Афанасия Фёдоровича среди членов «государева двора» бросалось в глаза: он и Богдан Бельский (племянник Малюты) во время приемов иностранных дипломатов в 1582–1583 годах стояли по обе стороны царского трона. Доверие к Нагому не было подорвано и планами нового брака царя — именно ему царь поручил вести дело о «сватовстве» к Марии Гастингс, родственнице английской королевы Елизаветы. При этом такие мелочи, как состояние жениха в браке, не смущали ни его, ни дядю царицы Марии.
Иван IV задумал это сватовство, чтобы укрепить союз с Англией и в то же время подготовить себе «политическое убежище». Он обратился к присланному Елизаветой медику Роберту Якоби с вопросом, нет ли для него в Англии подходящей невесты. Якоби и указал на Марию Гастингс, дочь владетельного князя. Богдану Бельскому, дьяку Андрею Щелкалову и Афанасию Нагому было поручено подробнее расспросить Якоби о невесте, что он и сделал: «Есть в Англинской земле удельного Тинтунского князя дочь, девка Мария Астин, а тот удел в Англинской земле большой, а девка лет в 30, а королеве Елисавете она племянница по матери».