После переговоров с венецианцами Хубилай задумал войти в сношения с Западом и решил отправить посольство к папе, поручив обоим братьям Поло быть его представителями перед папой. Купцы охотно согласились принять на себя эту миссию, облегчавшую им возвращение на родину. Хубилай приказал написать на турецком языке грамоту, в которой просил папу прислать ему сто учителей и ученых. Вместе с венецианцами хан отправил к папе своего приближенного Когатала.

В 1266 году братья Поло отправились в Европу. Но в дороге Когатал заболел, и венецианцы вынуждены были с ним расстаться. После долгих странствований, продолжавшихся три года, в 1269 году они достигли крепости Акка на Средиземном море и здесь узнали, что папа Климентий IV, к которому у них было послание от Хубилая, умер, а новый папа еще не был избран. Находившийся в Акке папский легат велел им дожидаться избрания папы. И тогда братья решили провести время ожидания на родине, где они не были уже пятнадцать лет. Маффео и Никколо отправились в Негропонт (Халкида), где сели на корабль, доставивший их прямо в Венецию.

В дороге Никколо узнал о смерти своей жены и о рождении сына, появившегося на свет через несколько дней после его отъезда, в 1254 году, и названного Марко. Оба брата прожили в Венеции два года, а избрание папы все откладывалось. Братья хорошо понимали всю важность ханского поручения и не сочли возможным откладывать далее возвращение к великому хану. Они снова отправились в Акку, взяв с собой и юного Марко, которому было тогда не более семнадцати лет. В Акке они получили у папского легата письмо к Хубилаю, в котором сообщалось о смерти папы Климентия IV. Но едва только они тронулись в путь, как узнали, что папский легат сам был избран папой под именем Григория X. Новый папа приказал гонцам вернуть путешественников с дороги и вручил им грамоты к великому хану, после чего венецианцы вторично отправились в далекий путь.

Здесь, собственно, и начинается путешествие Марко Поло. Посетил ли он в действительности все многочисленные страны и города, которые описывает в своей книге? Конечно, нет. В рассказе, написанном под его диктовку пизанцем Рустичано, прямо сказано, что «Марко Поло, умный и благородный гражданин Венеции, говорил о том, что видел своими глазами, и о том, чего сам не видел, но слышал от людей, нелживых и верных. И чтобы книга наша была правдива, истинна, без всякой лжи, о виденном станет говориться в ней как о виденном, а слышанное расскажется как слышанное; всякий, кто эту книгу прочтет или выслушает, поверит ей, потому что все тут правда».

Следует заметить, что в большей части упоминаемых им городов Марко Поло действительно бывал. Но во многих случаях все же трудно установить, когда путешественник описывает свои личные впечатления и когда сообщает сведения с чужих слов.

Возвращаясь в Монголию, братья Поло не придерживались того же самого пути, которым они следовали к великому хану в первый раз. Если прежде они ехали вдоль предгорий северного Тянь-Шаня, что значительно удлинило дорогу, то теперь они прошли более коротким путем – через нынешний Афганистан. Но, несмотря на это, их путешествие в резиденцию Хубилай-хана продолжалось около трех с половиной лет.

Марко Поло вместе со своим отцом и дядей Маффео начал путешествие с Малой Армении, которая характеризуется в его книге как «страна сильно нездоровая». «В старину, – сообщает путешественник, – здешние дворяне были храбры и воинственны; теперь они слабы и ничтожны и только пьянствуют». Большое впечатление произвел на венецианцев находящийся на берегу моря торговый город Лаяс (Аяс) – складочный пункт ценных азиатских товаров и место съезда купцов всех стран.

Великая Армения, которую затем посетил Марко Поло, представляла собой удобное становище для татарской армии. Путешественник упоминает о горе Арарат, где, по библейскому преданию, остановился ковчег Ноя во время всемирного потопа.