На путешествие из Бухары в Монголию братья Поло потратили целый год, пробираясь через многочисленные горные хребты Центральной Азии. Хубилай-хан был очень рад приезду венецианцев и с большим интересом расспрашивал их о событиях, происходивших в то время на Западе, о жизни и обычаях западноевропейских народов.
Братья Поло, свободно говорившие на монгольском языке, подробно отвечали на все вопросы хана.
После переговоров с венецианцами Хубилай задумал войти в сношения с Западом и решил отправить посольство к папе, поручив обоим братьям Поло быть его представителями перед главой церкви. Купцы охотно согласились принять на себя эту миссию, облегчавшую им возвращение на родину. Хубилай приказал написать на тюркском языке грамоту, в которой просил папу прислать ему сто учителей и ученых, чтобы идолопоклонников обратить в христианство. Вместе с венецианцами хан отправил своего приближенного Когатала и поручил ему привезти чуточку масла из той священной лампады, которая горит негасимым огнем на могиле Христа в Иерусалиме.
В 1266 г. братья Поло отправились в Европу. Но в дороге Когатал заболел, и венецианцы вынуждены были с ним расстаться. После долгих странствований, продолжавшихся три года, в 1269 г. они достигли крепости Акка на Средиземном море и здесь узнали, что папа Климентий IV, к которому у них было послание от Хубилая, умер, а новый папа еще не был избран. Находившийся в Акке папский легат велел им дождаться избрания папы. И тогда братья решили время до папских выборов провести на родине, где они не были уже пятнадцать лет. Маттео и Никколо отправились в Негропонт (Халкида), где сели на корабль, доставивший их прямо в Венецию.
В дороге Никколо узнал о смерти своей жены и о рождении сына, появившегося на свет через несколько дней после его отъезда в 1254 г. и названного Марко. Оба брата прожили в Венеции два года, а избрание папы все откладывалось. Братья хорошо понимали всю важность ханского поручения и не сочли возможным откладывать далее возвращение к великому хану. Они снова отправились в Акку, взяв с собой юного Марко, которому было тогда не более семнадцати лет. В Акке они получили у папского легата письмо к Хубилаю, в котором сообщалось о смерти папы Климентия IV. Но едва только они тронулись в путь, как узнали, что папский легат первого сентября 1271 г. был избран папой под именем Григория X. Новый глава церкви приказал вернуть путешественников с дороги.
Армянский царь предоставил в распоряжение Поло галеру, чтобы как можно быстрее доставить венецианцев в Акку. Папа принял их весьма поспешно, передал письма к китайскому императору, приставил к ним двух доминиканцев, Никколо из Виченцы и Гильермо из Триполи, а после благословил путешественников.
Простившись с его святейшеством, послы направились в Лаяс. Но едва они прибыли в этот город, как чуть не оказались пленниками банд мамелюкского султана Бибара, опустошавших тогда Армению. Оба доминиканца, обескураженные подобным началом путешествия, отказались от намерения ехать в Китай, переложив на венецианцев и Марко Поло заботу о передаче папского послания монгольскому императору.
Здесь, собственно, и начинается путешествие Марко Поло. Посетил ли он в действительности все многочисленные страны и города, которые описывает в своей книге? Конечно нет. В рассказе, написанном под его диктовку по-французски пизанцем Рустичано, прямо сказано, что «Марко Поло, умный и благородный гражданин Венеции, говорил о том, что видел своими глазами, и о том, чего сам не видел, но слышал от людей нелживых и верных. И чтобы книга наша была правдива, истинна, без всякой лжи, о виденном станет говориться в ней как о виденном, а слышанное расскажется как слышанное; всякий, кто эту книгу прочтет или выслушает, поверит ей, потому что все тут правда».
Следует заметить, что в большей части упоминаемых им городов и царств Марко Поло действительно бывал. Но во многих случаях все же трудно установить, когда путешественник описывает личные впечатления и когда сообщает сведения с чужих слов.
Возвращаясь в Монголию, братья Поло не придерживались того же самого пути, которым они следовали к великому хану в первый раз. Если прежде они ехали вдоль предгорий северного Тянь-Шаня, что значительно удлинило дорогу, то теперь они прошли более коротким путем — через нынешний Афганистан.
Но, несмотря на это, их путешествие в резиденцию Хубилай-хана продолжалось около трех с половиной лет.