Для сих переговоров из Москвы, осенью 1680 года, были отправлены посланниками полковник и стольник Василий Михайлович Тяпкин, долгое время бывший резидентом в Варшаве, и дьяк Посольского приказа Никита Моисеевич Зотов, известный тем, что обучал грамоте царевича Петра Алексеевича. Тяпкин по пути в Крым заехал в Батурин к гетману Самойловичу, который присоединил к московскому посольству писаря Прилуцкого полка Семена Раковина, знавшего татарский язык. Вместе с сим посольством ехал из Москвы крымский гонец Халиль-ага со своей свитой. От города Сум посланников провожал конвой в 600 человек, взятых частью из гетманских казаков, частью из рейтар Белгородского разряда. В статейном списке посольства, принадлежащем перу дьяка Зотова, находим любопытное описание перехода известным Муравским шляхом по степям, отделявшим тогда Московское государство от Крыма, – перехода трудного и крайне опасного вследствие нападений и грабежей от рыскавших по степи ногаев, калмыков и воровских казаков из Запорожья. В городке Валки путники вышли за укрепленную Белгородскую черту и вступили в открытую степь. Далее Муравский шлях шел по водоразделу между притоками с одной стороны Днепра, с другой – Дона и Азовского моря. По вершинам Орели, Самары, Тора, Конских, Овечьих и Молочных вод местность более или менее не лишена была рыбных речек и озер, сенных лугов и дубрав, обилующих зверями и дичью, а далее расстилалась уже голая безводная степь с выжженной травой; и люди, и кони должны были довольствоваться своими запасами, которые везли на телегах. На вершине Молочных вод начальник конвоя (майор Моканаков) взбунтовал рейтар и казаков, так что они, несмотря ни на какие убеждения посланников, покинули их и воротились домой. Путники после того шли с великим страхом от разбойников и по ночам отдыхали, держа в руках оружие и коней. Но затем начали встречаться пасшие стада перекопские татары, которые, благодаря вмешательству Халиль-аги, помогли посольству 19 октября благополучно добраться до города Перекопа. Он представлял небольшую четырехугольную крепость, окруженную каменной стеной и довольно глубоким рвом; а вокруг крепости теснились посады, состоявшие наполовину из жалких избенок и полотняных кибиток.
25 октября посольство остановилось в деревне на берегу речки Альмы, близ ханского стана; ибо хан на ту пору уехал из своей столицы Бахчисарая по поводу морового поветрия. Посланников и свиту поместили в каких-то каменных избах без потолков, без полов и дверей и не давали от хана корму ни им самим, ни их лошадям; приходилось все покупать, и дорогой ценой. Затем начались для них всякие мытарства и притеснения. Вместо того чтобы представить посланников ханову величеству, почти силой заставили Тяпкина прежде идти на поклон к ближнему ханову человеку Ахмет-аге; последний принял стольника высокомерно, сидя на коврах и облокотись на бархатные золотные подушки, одетый в зеленое суконное платье турецкого покроя на соболях и с белой чалмой на голове. Когда же посланники представились самому хану, то по уговору с Ахмет-агой дворцовые люди не брали их за шею, чтобы силой нагнуть до земли, и они сами сделали земной поклон. Мурад-Гирей сидел в углу палаты на красном бархатном ковре, опершись на золотные подушки. Он был среднего роста, довольно красив; волосы имел черные с проседью, а бороду красил; платье его также было белого сукна и турецкого покроя, а исподний кафтан тофтяной алого цвета, шапка татарская красного сукна с собольей опушкой. По обеим сторонам его стояли ближние люди, частью в турецком, частью в татарском наряде, кто в чалме, кто в шапке. Посланники проговорили свою речь по наказу, подали государеву грамоту, завернутую в тафту, и поднесли поминки из сороков соболей. Хан спрашивал о здоровье великого государя, не снимая шапки. Он пожаловал посланникам золотные кафтаны, которые тут же на них и надели. Потом посланники были с поклоном у царевичей, или салтанов, Калги и Нурадина, говорили им речи по наказу и поднесли поминки при таких же церемониях, как у хана. Каждый из них также принимал посольство, сидя на бархатном ковре с подушками, имея ближних людей, стоявших по обе стороны, и также отдаривал золотыми кафтанами. Посланникам разрешили съездить в Жидовский городок (Чуфут-Кале), чтобы повидаться там с пленным боярином В.Б. Шереметевым, которому они привезли жалованье от царя червонным золотом и соболями; отдали царское жалованье и другому пленнику, стольнику князю Андрею Ромодановскому. Шереметев потом был призываем к участию в мирных переговорах, которые велись со стороны хана Ахмет-агой и другими ближними людьми.