Царь велел также взять в Архангельске надежного «целовальника» (казначея, дававшего клятву честности на кресте) для хранения «государевой соболиной казны», которую послы везли в подарок тосканскому герцогу и его приближенным.
8 июля 1659 г. делегация выехала из Москвы в Архангельск и прибыла на место лишь и августа. Еще месяц посланники прожили в Архангельске, в ожидании прибытия и погрузки двух английских кораблей, идущих вокруг Европы. 21 сентября, отслушав молебен в Преображенском соборе, Лихачев, Фомин и их товарищи (всего 24 человека) отправились, в сопровождении отряда стрельцов, в морскую гавань на Мосеевомострове, откуда и началось плавание. Английские купеческие корабли были выбраны в том числе потому, что Англия в те годы находилась в хороших отношениях с Оттоманской Портой, и под защитой английского флага московские послы могли не опасаться нападения «турских воровских людей», господствовавших в Средиземноморье. Плавание началось с несчастья: на третий день умер переводчик с итальянского Тимофей Топоровский (его отсутствие потом сильно скажется в Италии), и священнику Алексееву пришлось совершить отпевание и погребение в море.
Обогнув Европу и пройдя Гибралтарский пролив, корабли с русским посольством вошли 9 ноября 1659 г. в Средиземное море. Лихачев с удивлением отметил в «Статейном списке»:
«На том море дни стали светлы и красны, как у нас о Троицыне дне, а тут о Филиппове заговенье таковы: а дни и ночи одинаковы».
Однако почти сразу начались сильные штормы – как и три года назад, когда тем же путем из Архангельска в Ливорно направлялось посольство Чемоданова и Посникова, потерявшее тогда большую часть взятого с собой коммерческого товара и сильно повредившее дорогие сибирские меха, предназначенные для венецианцев. На этот раз, для облегчения кораблей, пришлось сбросить в море часть съестных припасов и бочек с пресной водой – к концу путешествия из-за недостатка питьевой воды приходилось собирать на палубе дождевую воду. В «Статейном списке» посольства имеются записи: «После бури на море, посланники воздавали Христу Богу молебное пение…»
5 января 1660 г., уже в виду гавани Ливорно – главного морского порта Тосканы (полностью заменившего к тому времени Пизу из-за обмеления устья Арно), сильнейшая буря так повредила корабли, что они еле смогли бросить якоря. Команда и пассажиры прошли строгий пограничный контроль из-за угрозы занесения «морового поветрия»: тосканская стража каждого «разболокала» (раздела) и внимательно осмотрела.