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