Шемахе, принадлежавшей тогда государю Медии и вассалу персидского шаха. Обрадованный встречей, венецианец упросил русского посла взять его с собой, и Марк согласился тайно провезти его в своей свите в Московию.
6 ноября того же года они выехали в Дербент, лежавший тогда, по словам Контарини, «на границе Татарии». По совету опытных людей в это время года невозможно было пускаться в такое далёкое путешествие, через степи татар, равно как и по бурному Каспийскому, или, как его называет Контарини, Бакинскому морю. Поэтому Марк решил зазимовать в Дербенте, с тем, чтобы в апреле переправиться на судах через море в «Питрахань» (то есть Астрахань).
Хотя Контарини и хвалит добродушие мусульман, жителей Дербента, но из того же его рассказа видно, что ему приходилось скрывать от них и своё настоящее звание, и национальность. Описывая свои странствования за провизией по рынкам Дербента, Контарини сообщает: «Иногда прохожие, глядя на меня, останавливались и говорили друг другу — тот человек не рождён для того, чтобы самому таскать тяжести». В изорванном овчинном тулупе и бараньей шапке, то есть подлинно русской одежде, вероятно, данной ему русским послом, чтобы придать Контарини вид одного из своих слуг, Марк скрывал его от местных властей, которые безусловно лишили бы его жизни, если бы звали правду. Эго показывает на тогдашние взаимоотношения государств Западной Европы и Азии, так как русский посол мог открыто зимовать в владениях азиатского царька со своей свитой, пользуясь при этом полной безопасностью и авторитетом, в то время, как посол Венеции должен был скрываться и трепетать за свою жизнь и судьбу.
Из книги Контарини явствует, что русский посол свободно владел татарским, персидским и итальянским языками, если объяснялся как с ним самим, так и понимал разговор жителей Дербента. Очевидно, что Контарини не только ценил знание языков и уважение к Марку в этих полудиких странах, его практическую опытность, необходимые в столь опасных и трудных путешествиях. Он вообще смотрел на русского коллегу, как на своего защитника и покровителя. В своей книге Контарини наивно признаётся, что однажды, когда Марк выехал по делам на три дня из города, «мы, бедные итальянцы, оставшись без него, натерпелись много страха».
6 апреля Марк нанял судно для переезда в Астрахань, и они благополучно вышли в море. На борту оказалось 25 душ вместе с двумя посольствами и персидскими купцами, отправлявшимися в Астрахань за товарами. Все туземцы продолжали с подозрением относиться к Контарини и его свите, и их успокоили только уверения Марка, что Контарини будто бы сын придворного врача московской великой княгини Софии Фоминичны, и что он едет в Москву искать счастья при тамошнем дворе.
Только на двадцать четвёртый день бурного плавания по Каспию, где судно едва не погибло, а пассажиры его голодали, они добрались до Астрахани. День праздника Пасхи им пришлось провести в глухих камышах, где они разговелись десятью утиными яйцами, разысканными людьми Марка, и которыми русский посол великодушно поделился с итальянцами.
В Астрахани Контарини и его трёх людей татары отказались выпустить на берег, и только по ходатайству Марка перед местным ханом их выпустили и доставили в дом, где уже находился русский посол со своей свитой. Марк Толмач таким образом, по словам Контарини, повсюду являлся его ангелом-хранителем. Влияние Марка в пограничных с Россией владениях указывало также и на то обстоятельство, что он далеко не впервые ездил по этим местам, так как имел связи даже в далёкой Астрахани.
«На другой день после нашего приезда в Астрахань, — повествует Контарини далее, — пришли к нам трое татар с лицами узкими и плоскими, как доски, и потребовали меня к хану, объявив одновременно, что Марку опасаться нечего, ибо он друг их государю, но что я, как франк, их враг и должен стать его рабом. Марк взялся отвечать за меня, советуя мне молчать и предаться совершенно его покровительству».
Опасность для итальянцев, несмотря на защиту русской миссии, всё время увеличивалась, и им объявили, что они будут проданы на рынке. Контарини пришлось заплатить за себя, чтобы не быть проданным в рабство, хану 2000 талеров, не считая всевозможных подарков. Как деньги, так и подарки ему пришлось занять у Марка и у татарских купцов под его же поручительство. Хан был удовлетворён, но на том дело не кончилось, так как татарские чиновники, пользуясь каждый раз выходом из дома русского посла, требовали с Контарини «страшным голосом и грозясь посадить его на кол», выдачи им всех драгоценностей.
Всё это, несомненно, показывает, что Марко Росс был весьма влиятельным и значительным лицом в Астрахани, если за его одним поручительством чужие люди доверили большие суммы неизвестному иностранцу и в его присутствии варвары-татары не смели тревожить его спутников.
Из Астрахани Марк с Контарини выехали 10 августа 1476 года с тем, чтобы сесть, когда едва стемнеет, на барку, стоящую на берегу
