В эту эпоху такое далёкое путешествие было тяжёлым испытанием, и было преисполнено столькими опасностями, что Контарини готовился к нему, как почти к верной смерти. Он не только исповедался и причастился, но и как умирающий навсегда попрощался со всеми родными и близкими.
Через Германию, Польшу, Дикое поле он добрался до Каффы, теперешней Феодосии, где погрузился на корабль, шедший в Мингрелию. Отсюда через Кавказ и Армению он прибыл в Тавриз. Окончив свою миссию, Контарини отправился в обратную дорогу, в сопровождении посла великого князя Московского и Белой Руси (del Duca di Moscovia, signor della Rossia Bianca) Марко Росса, с которым он познакомился и сошёлся в Тавризе. Это был посол Ивана III — Марк, по прозванию Толмач, которого Контарини, ввиду его русского происхождения, именует «Марко Росс».
Они вместе выехали из Персии через Тифлис и Кутаис в г. Фазис (теперешнее Поти) для того, чтобы погрузиться затем на корабль в Каффу. Перенеся по дороге всякого рода притеснения и грабежи, в Фазисе они узнали роковую для обоих весть, что страшные для всех турки-оттоманы овладели генуэзской колонией Каффой, через которую каждый из них надеялся безопасно вернуться на родину.
Приходилось выбирать другой путь, и Марко Толмач, по-видимому, более знакомый с местностью и условиями, повернул назад, чтобы через владения Григория — государя Халцихана и Бати, городов, пограничных с турками, ехать через Шемаху к берегам Каспийского моря на Дербент и Астрахань.
Что касается Контарини, то он по неопытности предпочёл остаться в Фазисе, хотя и дорожил спутничеством русского посла.
Оставшись со своими четырьмя спутниками без всяких средств и помощи среди дикого и враждебного ему населения, страдая жестокой кавказской лихорадкой, Контарини вскоре бросился догонять Марка. 17 сентября 1475 года он догнал его в Шемахе, принадлежавшей тогда государю Медии и вассалу персидского шаха. Обрадованный встречей, венецианец упросил русского посла взять его с собой, и Марк согласился тайно провезти его в своей свите в Московию.
6 ноября того же года они выехали в Дербент, лежавший тогда, по словам Контарини, «на границе Татарии». По совету опытных людей в это время года невозможно было пускаться в такое далёкое путешествие, через степи татар, равно как и по бурному Каспийскому, или, как его называет Контарини, Бакинскому морю. Поэтому Марк решил зазимовать в Дербенте, с тем, чтобы в апреле переправиться на судах через море в «Питрахань» (то есть Астрахань).
Хотя Контарини и хвалит добродушие мусульман, жителей Дербента, но из того же его рассказа видно, что ему приходилось скрывать от них и своё настоящее звание, и национальность. Описывая свои странствования за провизией по рынкам Дербента, Контарини сообщает: «Иногда прохожие, глядя на меня, останавливались и говорили друг другу — тот человек не рождён для того, чтобы самому таскать тяжести». В изорванном овчинном тулупе и бараньей шапке, то есть подлинно русской одежде, вероятно, данной ему русским послом, чтобы придать Контарини вид одного из своих слуг, Марк скрывал его от местных властей, которые безусловно лишили бы его жизни, если бы звали правду. Эго показывает на тогдашние взаимоотношения государств Западной Европы и Азии, так как русский посол мог открыто зимовать в владениях азиатского царька со своей свитой, пользуясь при этом полной безопасностью и авторитетом, в то время, как посол Венеции должен был скрываться и трепетать за свою жизнь и судьбу.
Из книги Контарини явствует, что русский посол свободно владел татарским, персидским и итальянским языками, если объяснялся как с ним самим, так и понимал разговор жителей Дербента. Очевидно, что Контарини не только ценил знание языков и уважение к Марку в этих полудиких странах, его практическую опытность, необходимые в столь опасных и трудных путешествиях. Он вообще смотрел на русского коллегу, как на своего защитника и покровителя. В своей книге Контарини наивно признаётся, что однажды, когда Марк выехал по делам на три дня из города, «мы, бедные итальянцы, оставшись без него, натерпелись много страха».
6 апреля Марк нанял судно для переезда в Астрахань, и они благополучно вышли в море. На борту оказалось 25 душ вместе с двумя посольствами и персидскими купцами, отправлявшимися в Астрахань за товарами. Все туземцы продолжали с подозрением относиться к Контарини и его свите, и их успокоили только уверения Марка, что Контарини будто бы сын придворного врача московской великой княгини Софии Фоминичны, и что он едет в Москву искать счастья при тамошнем дворе.
Только на двадцать четвёртый день бурного плавания по Каспию, где судно едва не погибло, а пассажиры его голодали, они добрались до Астрахани. День праздника Пасхи им пришлось провести в глухих камышах, где они разговелись десятью утиными яйцами, разысканными людьми Марка, и которыми русский посол великодушно поделился с итальянцами.
В Астрахани Контарини и его трёх людей татары отказались выпустить на берег, и только по ходатайству Марка перед местным ханом их выпустили и доставили в дом, где уже находился русский посол со своей свитой. Марк Толмач таким образом, по словам Контарини, повсюду являлся его ангелом-хранителем. Влияние Марка в пограничных с Россией владениях указывало также и на то обстоятельство, что он далеко не впервые ездил по этим местам, так как имел связи даже в далёкой Астрахани.
«На другой день после нашего приезда в Астрахань, — повествует Контарини далее, — пришли к нам трое татар с лицами узкими и плоскими, как доски, и потребовали меня к хану, объявив одновременно, что Марку опасаться нечего, ибо он друг их государю, но что я, как франк, их враг и должен стать его рабом. Марк взялся отвечать за меня, советуя мне молчать и предаться совершенно его покровительству».
Опасность для итальянцев, несмотря на защиту русской миссии, всё время увеличивалась, и им объявили, что они будут проданы на рынке. Контарини пришлось заплатить за себя, чтобы не быть проданным в рабство, хану 2000 талеров, не считая всевозможных подарков. Как деньги, так и подарки ему пришлось занять у Марка и у татарских купцов под его же поручительство. Хан был удовлетворён, но на том дело не кончилось, так как татарские чиновники, пользуясь каждый раз выходом из дома русского посла, требовали с Контарини «страшным голосом и грозясь посадить его на кол», выдачи им всех драгоценностей.
Всё это, несомненно, показывает, что Марко Росс был весьма влиятельным и значительным лицом в Астрахани, если за его одним поручительством чужие люди доверили большие суммы неизвестному иностранцу и в его присутствии варвары-татары не смели тревожить его спутников.
Из Астрахани Марк с Контарини выехали 10 августа 1476 года с тем, чтобы сесть, когда едва стемнеет, на барку, стоящую на берегу Волги. «Вдруг Марк, — говорит Контарини, — окликнул меня таким голосом, что я подумал, что настал мой последний час, и велел мне сесть на коня и скакать в сопровождении одного татарина с самой отвратительной рожей». Итальянец, не противореча и ничего не спрашивая, ехал вслед за татарином двое суток. На вопрос посла татарин объяснил, что хан приказал осматривать все отходящие по Волге лодки и «если бы я был там найден, то был бы наверное задушен». Татарин скрыл Контарини на острове, куда через три дня Марк прислал за ним своего человека.
В дальнейшем путешественники двинулись вдоль берега Волги. Посол Марк начальствовал над караваном, который состоял из 300 человек русских и татар, имевших при себе 500 лошадей, как заводных, так и для прокормления в пути.
Через 15 дней пути караван переправился на другой берег и, связав плоты по 40 брёвен в каждом, привязал их к хвостам коней, которыми правили татары, и эти лошади тащили паромы.
Проехав неохватные пространства степи без дорог и жилья, послы добрались, наконец, до рубежей Рязанской области, откуда через Коломну прибыли в Москву.
Марк поместил Контарини в своём собственном доме, снабдил его всем необходимым и «именем государя своего убеждал быть спокойным и почитать себя как бы в собственном доме». Поблагодарив его за спасение жизни, Контарини просил представить его великому князю. «В скором времени я получил приказание явиться во дворец, где, после обычных приветствий, отблагодарил великого князя за внимание, оказанное мне его послом Марком, который поистине неоднократно спасал меня от великих опасностей».