Marco Polo zrelacjonował ten epizod dość oględnie. Możemy się tylko domyślać, że bracia Polo niepostrzeżenie z wędrownych kupców przemienili się w wędrowców i poszukiwaczy nowych szlaków i kontaktów handlowych. Po trzech latach pobytu w Bucharze znalazł ich tam przypadkiem poseł chana Hulagu, który panował w Iranie, i zachęcił do dalszej wspólnej podróży aż do Chanbałyku (dzisiejszy Pekin). Po roku uciążliwej wędrówki przybyli wraz z posłem na dwór wielkiego chana Kubilaja, gdzie – zgodnie z zapewnieniami usłyszanymi w Bucharze – zostali przyjęci hojnie i życzliwie. Obyty i ciekawy nowin władca mongolskiego imperium powierzył niecodziennym przybyszom osobistą misję. Mieli zawieźć papieżowi oficjalny list i wrócić z odpowiedzią w towarzystwie stuosobowego kolegium chrześcijańskich uczonych przysposobionych do poważnych dyskusji oraz z oliwą z lampki palącej się w Bazylice Grobu Pańskiego w Jerozolimie (to dla matki chana, która była chrześcijanką – zapewne wyznania nestoriańskiego). Chociaż zostali zaopatrzeni w złotą tablicę z pieczęcią wielkiego chana, która gwarantowała bezpieczeństwo i przywilej korzystania z wszelkich udogodnień podczas podróży, droga powrotna przez Azję zajęła włoskim kupcom aż trzy lata. Marco Polo tłumaczył, że jego ojca i stryja powstrzymywała niesprzyjająca aura. A może włoscy kupcy przeobrazili się już po części w turystów obieżyświatów i dlatego się nie spieszyli? Dopiero w kwietniu 1269 roku dotarli do Akki, tętniącego życiem portu, ośrodka handlowego oraz potężnej twierdzy, która była ostatnim bastionem krzyżowców na Bliskim Wschodzie. Tam dowiedzieli się o śmierci papieża Klemensa IV i o skłóconym kolegium kardynalskim niezdolnym do wyboru nowego papieża. Opowiedział im o tym legat papieski Tebaldo Visconti z Piacenzy i zalecił czekać. W tej sytuacji podróżnicy po kilkunastu latach wrócili do rodzinnej Wenecji: Niccolo zobaczył po raz pierwszy swego syna Marco.
Wakat na tronie papieskim przedłużał się i wiosną 1271 roku bracia Polo stracili cierpliwość: postanowili wrócić na dwór Kubilaja, choć nie wypełnili misji w całości. Wraz z nimi w swoją wielką życiową podróż wyruszył 17-letni Marco. Podróżnicy dopłynęli do Akki i otrzymali od legata Viscontiego upoważnienie do zabrania odrobiny oliwy z lampki w Bazylice Grobu Pańskiego w Jerozolimie. Zaopatrzywszy się w cenną substancję, ruszyli do Chin. Pierwszym znaczącym przystankiem w podróży był Lajas w Małej Armenii (założonej w XI wieku przez ormiańskich uchodźców na południu Anatolii). W tym ośrodku kupieckim kończył się szlak karawan z Azji Środkowej i Persji: „Wszystkie korzenie – relacjonował Marco Polo – i tkaniny jedwabne, złotem przetykane i wełniane oraz inne kosztowne rzeczy zwożone są z głębi lądu do miasta. Bawełny jest też dużo, a kupcy z Wenecji, Pizy i Genui oraz ze wszech stron przybywają tu, aby czynić zakupy i sprzedawać swe własne towary; mają swe składy w mieście”. W Lajas dogoniła Wenecjan niespodziewana nowina: ich protektor Tebaldo Visconti został nowym papieżem (przyjął imię Grzegorza X) i zalecił im powrót. Raz jeszcze ugościł ich w Akce, zaopatrzył w oficjalne listy do chana, przydzielił dwóch dominikanów, brata Mikołaja z Vicenzy i brata Gwilema z Trypolisu (którzy jednak dość szybko przelękli się niebezpieczeństw i zawrócili), oraz wyprawił w drogę.
Wenecjanie przemierzyli Anatolię. Jak przystało na potomka weneckich kupców, Marco Polo wszędzie zwracał uwagę na najciekawsze produkty i towary. Tam jego oczy cieszył widok „najdelikatniejszych i najpiękniejszych dywanów”, a w Wielkiej Armenii zauważył „bukaran” (czyli bukram: cenioną w średniowieczu tkaninę z bawełny, której nazwa wskazywała, że wytwarzana była pierwotnie w Bucharze). Dłużej niż dwa dni objeżdżali majestatyczną górę Ararat, podziwiali jej pokryty śniegiem wierzchołek, na którym osiadła po potopie arka Noego (dlatego Marco Polo nazywał ją Górą Arki). Na granicy z Gruzją (Żorżania) podróżnicy natrafili na osobliwe źródło, z którego „płynie olej w tak wielkiej obfitości, że napełnić nim można by naraz sto okrętów; nie nadaje się do jedzenia, lecz dobry jest do palenia i do smarowania ludzi i zwierząt chorych na świerzb oraz wielbłądów chorych na parchy i krosty. Ludzie z odległych stron przybywają po ten olej i cała okolica pali tym olejem tylko”. Marco Polo był pierwszym europejskim podróżnikiem, który opisał występowanie i zalety nafty. Na Kaukazie zdumiał go wąski przesmyk Derbent między łańcuchem gór a Morzem Kaspijskim (w dzisiejszym Dagestanie). Znajdowały się tam obwarowania, czyli legendarne Żelazne Wrota, którymi Aleksander Wielki odgrodził niegdyś swoje imperium przed straszliwymi koczownikami z Północy, może samymi ludami Goga i Magoga.
Weneccy podróżnicy skierowali się na południe, na ziemie dzisiejszego Iraku. Ich szlak prowadził przez Mosul i Bagdad do Zatoki Perskiej. Marco Polo stale zbierał ciekawe i zarazem praktyczne dla wędrownych kupców informacje o ludach, ich religii i zwyczajach: „W górach tego kraju mieszka lud zwany Kurdami. […] Jest to lud wojowniczy, ale zbójecki. Chętnie łupią kupców, jeśli ci zapuszczą się z towarami w kraj przez nich zamieszkany”. Wszędzie oceniał walory gospodarcze poznawanych krajów.
I tak zapamiętał, że Mosul słynął z produkcji jedwabnych tkanin przetykanych złotymi nićmi, czyli muślinu (nazwa pochodzi od miejsca wyrobu). Bagdad widział jako bogaty ośrodek wyrobu doskonałych tkanin i kosztowności, a przy okazji przytoczył ponurą anegdotę o śmierci ostatniego bagdadzkiego kalifa z dynastii Abbasydów al Mustasima. Po zdobyciu Bagdadu w 1258 roku chan Hulagu – brat Kubilaja – miał zdumiewać się wieżą pełną złota i innych kosztowności, a jeszcze bardziej zadziwił się głupotą kalifa, który nie użył swoich skarbów do zorganizowania obrony lub nie przeznaczył ich na okup. Zdobywca udzielił swemu chciwemu i skąpemu jeńcowi okrutnej lekcji: zamknął go w wieży i kazał mu się żywić skarbami, czym doprowadził go do śmierci głodowej. „Zaiste lepiej byłoby dlań rozdać skarb ludziom, aby bronili ziemi jego i ludu, niż zginąć wydziedziczonym wraz z całym narodem” – tak sentencjonalnie zakończył tę historię Marco Polo.
Z Iraku trójka Wenecjan przepłynęła do cieśniny Ormuz. Być może pierwotnie planowała dotrzeć do Chin drogą morską, szlakiem doskonale znanym arabskim żeglarzom? Ostatecznie zdecydowali się jednak wyruszyć drogą lądową, skręcając na północ i maszerując skrajem Persji ku Afganistanowi. Być może skłoniły ich do tego przestrogi o czyhających niebezpieczeństwach, może wieści o nieprzyjaznym nastawieniu władcy i ludności na południu Chin: dogorywała tam chińska dynastia Sung, która wkrótce miała ulec Mongołom. Zauważmy, że wielki chan Kubilaj miał swoje siedziby w północnych Chinach. Tak czy inaczej ten etap wędrówki Wenecjanie rozpoczęli od miasta Taurus (czyli Tebriz), które dzięki korzystnemu położeniu było wielkim targowiskiem. Przyjeżdżali tam kupcy z Iraku, Indii oraz z Włoch. Marco Polo zapamiętał, że w perskich miastach rzemieślnicy wyrabiali cenne złotogłowy i inne tkaniny jedwabne oraz bawełniane i że kupcy musieli wędrować z dobrze uzbrojoną strażą. Od rozmaitych ludzi usłyszał nieodległą historię Starca z Gór, jego zamku i wspaniałego ogrodu oraz wyrachowanego sposobu werbowania do sekty assasynów młodzieńców gotowych popełnić na jego rozkaz każdą najśmielszą zbrodnię. Starzec z Gór czynił to tak: odurzonych opium młodzieńców kazał przenosić do swego ogrodu, następnie pozwalał im rozkoszować się jadłem i urodziwymi dziewczętami, po przebudzeniu zaś wmawiał im, że przebywali w raju, do którego z pewnością wrócą po śmierci. Kres ich terrorystycznej działalności położyły dopiero wojska chana Hulagu, które po trzyletnim oblężeniu zdobyły i zniszczyły górską twierdzę assasynów (w 1256 roku). Weneccy kupcy wędrowali dalej przez pustynie, oazy i miasta. Napotykali rozmaite wspólnoty: „czcicieli ognia”, czyli zaratustrian, nestorian, jakobitów oraz inne grupy chrześcijan, także muzułmanów, którzy gotowali wino, a następnie raczyli się słodkim skondensowanym napojem i tym sposobem chytrze obchodzili zakaz nałożony na nich przez Proroka. Wędrowcy dostrzegali często ślady zniszczeń dokonanych przez najazdy mongolskie, ale i odradzającą się wspaniałość mijanych osad. Trudy wędrówki wyostrzały apetyt: zapamiętali smak najsłodszych na świecie melonów, krojonych w cienkie plastry i suszonych na słońcu. Skosztowali ich w Sapurgan (dzisiejszy Szibargan w północnym Afganistanie). Kiedy po trzech dniach wędrówki przez bezludzie dotarli do Badachszanu, ich największą ciekawość wzbudziły informacje o kopalniach okazałych rubinów. Jako kupcy łatwo zrozumieli zapobiegliwe postępowanie lokalnego władcy, który zmonopolizował obrót szlachetnymi kamieniami. Marco Polo wspominał po latach: Postępuje tak król, aby rubiny jego zachowały cenę i wartość, jaką mają. Zaś gdyby pozwolił, aby inni ludzie kopali je i rozwozili po świecie, wydobywano by je w tak wielkiej ilości, że straciłyby wartość i spadłyby w cenie. Panowała w tej krainie dziwnie żywa pamięć o Aleksandrze Macedońskim. Od niego wywodzili władcy Badachszanu swe szczytne pochodzenie, a rasa koni królewskich brała początek od rumaka Aleksandra Macedońskiego Bucefała.