Paljon vastusteltuaan Kublai vihdoin suostui tähän ehdotukseen, ja venezialaiset pääsivät lähtemään. Suurkaani varusti laivaston, johon kuului neljätoista laivaa, ja kahden vuoden eväät. Toiset laivoista olivat niin suuria, että niissä oli 250 mieheen laivaväkeä. Retkikunta oli siis kerrassaan suurenmoinen ja Kiinan mahtavan hallitsijan arvon mukainen.
Kiinalaiset olivatkin niihin aikoihin taitavampia laivanrakentajia ja ehkä purjehtijoitakin kuin länsimaalaiset. Laivat olivat petäjästä rakennetut, rautanauloilla naulatut ja kannelliset. Tavallisesti niissä oli neljä mastoa ja purjetta. Kannen alla oli viisi- tai kuusikymmentä kajuuttaa, joissa kauppiaat saattoivat järjestää olonsa niin mukavaksi kuin suinkin. Vielä merkillisempää on, että laivat oli vedenpitävillä väliseinillä jaettu osastoihin, niin etteivät ne uponneet, vaikka niihin tulikin reikä, esim. yhteentörmäyksessä valaan kanssa, ja reikä saatettiin merellä ollessa korjata. Liitokset oli tukittu hampulla ja kalkin ja puuöljyn sekotuksella. Joka laivassa oli monta erikokoista pelastusvenettä, jotka purjehdittaissa ripustettiin laivan kyljille, ja pari kolme hyvin suurta. Kiinalaisten laivat olivat siis kehittyneet monessa suhteessa yhtä pitkälle kuin Länsimaitten suuret purjelaivat vasta joku vuosisata myöhemmin. Mutta siitä ne eivät ole sen koommin parantuneet, vaan ovat yhä vielä jotenkin samalla kannalla kuin Marco Polon aikana.
Samanlaisilla laivoilla Kublai kaan oli vähällä vallottaa Japanin eli Zipangun, jonka kullanrikkaudesta Marco Polo kertoo ihmeitä: mutta tuo suurisuuntainen yritys raukesi tyhjiin päälliköitten eripuraisuuden ja hirmumyrskyn vuoksi, joka arvatenkin tuhosi suurimman osan laivastosta. Marco Polo ei nähtävästi ollut itse mukana sillä retkellä, mutta sen kautta hän kuitenkin saattoi tuoda Japanista Länsimaille ensimäiset tiedot. Hän kertoo asukkaitten olevan valkoisia ja hyvin muodostuneita, mutta saaren olevan niin kaukana valtameressä, että sinne harvoin kulki kauppiaita. Kultaa kun ei saanut viedä maasta pois, niin sitä muka kokoontui sinne niin runsaasti, että kuninkaallisen palatsin katto oli kokonaan kullasta ja lattiat kaksi sormea vahvoista kultalevyistä. Nämä tarumaiset kertomukset Zipangun rikkauksista tekivät sitten syvän vaikutuksen Länsimailla. Columbus, joka ei tiennyt Amerikkaa välillä olevankaan ja luuli maapalloa paljon pienemmäksi, kuin se todellisuudessa on, saattoi hyvällä syyllä otaksua valtameren poikki purjehdittuaan tulevansa Zipanguun. Sen huhuttu kultarikkaus oli yhtenä suurena yllykkeenä hänen matkaansa.
Polojen johtama laivasto lähti matkaan Zaytonista (luultavasti nykyisestä Tshangtshousta, Amoy lahdesta), joka oli Etelä-Kiinan suurin satamakaupunki. Purjehdittiin pitkin Taka-Intian rantoja, mutta merenkulkijoilta Marco Polo sai tietoja Filippineistä ja Maustesaarista eli Molukeista, vaikka hän luuli niitten olevan paljon kauempana meressä kuin ne todellisuudessa ovat. »Näitten saarien rikkaus tosiaan on ihmeteltävä», hän lausui, »mutta matkaan kuluu kokonainen vuosi, sillä sinne lähdetään talvella ja palataan vasta seuraavana kesänä.» Merellä nimittäin vallitsi ainoastaan kaksi tuulta, toinen auttoi laivoja menomatkalla, toinen paluumatkalla, toinen puhalsi koko talven, toinen koko kesän. Tämä tieto perustuu tosiasioihin; mainitut tuulet ovat Itä-Aasian monsuunituulet, jotka puhaltavat, talvimonsuuni luoteesta, kesämonsuuni vastakkaisesta suunnasta.
Kotshin-Kiina eli Tshamba, jonka Kublai kaan oli vallottanut, oli ensimäisiä pysäyspaikkoja matkalla. Sieltä Marco Polo purjehti etelää tai kaakkoa kohti »maailman suurimman saaren», Jaavan ohi. Jaava oli laajalti kuulu rikkaudestaan ja kehittyneestä sivistyksestään. Siellä tehtiin loistavia kauppoja, sillä saaressa oli runsaasti kaikkein arvokkaimpia tavaroita. Varsinkin siellä oli viljalta kaikenlaisia maustimia. Suurkaani olisi mielellään vallottanut tämän rikkaan saaren, ellei se olisi ollut niin kaukana.
Kiinalainen laivasto purjehti sitten edelleen Sumatraan, jota sanottiin »Pieneksi Jaavaksi», vaikka se toden teolla on varsinaista Jaavaa monta vertaa suurempi. Polo sanoo saaren olevan niin kaukana etelässä, että Pohjantähti siellä katoo taivaanrannan alle, joten merimiehet siellä helposti joutuivat eksyksiin. Laivasto viipyi, arvatenkin tuulia odotellen, sillä rannikolla viisi kuukautta ja Pololla oli siis hyvä tilaisuus tehdä havainnoita. Saaren troopillista kasvullisuutta hän ihasteli, mutta asukkaat olivat kamalia ihmissyöjiä. Marco Polo tutustui Sumatrassa kookospähkinään ja sagopalmuun. Sitä paitsi siellä kasvoi mitä parasta kamferia, joka oli kultaakin kalliimpaa. Edelleen poikettiin Nikobareilla ja Andamaneilla, joitten asukkaat olivat erinomaisen raakoja, miehillä pää kuin koiralla. Andamaneilta tultiin Seilaniin (Ceyloniin), jonka korkealla kukkulalla sanottiin olevan Aatamin haudan. Niin muhamettilaiset väittivät, jota vastoin pakanat väittivät sitä Buddhan haudaksi. Seilanissa oli kaikenlaisia jalokiviä loppumaton rikkaus ja sen kuninkaalla oli maailman kaunein rubiini, tahraton ja rikas kuin tuli. Kublai oli tahtonut ostaa tämän valtavan suuren jalokiven, mutta kuningas ei sitä myynyt. Polo ennätti kerätä mieltäkiinnittäviä tietoja ikivanhasta helmenkalastuksesta, jota harjotettiin Ceylonin ja mannermaan välillä ja kertomus vastaa täydelleen nykyaikaisiakin oloja. Ceylonin asukkailta Polo sai tietoja vastapäätä olevasta Etu-Intian osasta, Maabarista (Malabarista), muun muassa Hindujen uskonnosta ja kastijaosta. Paariat, jotka olivat alin kasti, olivat muka joutuneet onnettomaan asemaansa sen kautta, että olivat murhanneet apostoli Tuomaan, kun hän kävi Intiassa kristinoppia saarnaamassa. Apostolin hauta oli lähellä Madrasia Intian rannikolla ja sitä pidettiin suuressa kunniassa.
Timanttien saannista Polo kuuli tuon vanhan itämaalaisen tarun, jonka olemme ennen jo usean kerran maininneet. »Eräässä osassa Intiaa on korkeita vuorenkukkuloita, joille on mahdoton nousta. Mullassa, jota ankarat rankkasateet viruttavat näitten vuorenhuippujen kyljiltä, on paljon timantteja, joita sateen lakattua löydetään purojen uomista. Mutta niiden etsiminen on ylen vaarallista, osasta ankaran kuumuuden, osasta myrkyllisten käärmeitten vuoksi, joita maa kiehuu täynnään. Varsinkin eräisiin syviin laaksoihin, joihin on mahdoton päästä, on timantteja aikain kuluessa keräytynyt. Sen vuoksi menetellään seuraavalla tavalla. Näihin kalliorotkoihin heitetään lihakappaleita. Kun vuoristossa elävät valkoiset kotkat näkevät ne, niin ne lentävät alas ja ottavat lihakappaleet kynsiinsä sekä kantavat jollekin vuorenkukkulalle, syödäkseen siellä saaliinsa. Mutta väjymässä olevat pyyntimiehet alkavat silloin elämöidä kovasti, niin että pelottavat kotkat lihan luota. Miehet rientävät ottamaan lihakappaleet, joihin on rotkon pohjalta tarttunut runsaasti timantteja. Näitten lintujen pesistäkin löydetään paljon jalokiviä, ja usein niitä on löydetty kotkien vatsasta.» Intian timantit olivat muka paljon kauniimpia kuin Europassa tavatut, sillä kauneimmat jalokivet ja helmet vietiin aina suurkaanille ja muille itämaisille ruhtinaille, joilla sen vuoksi oli maailman parhaat aarteet. Ainoastaan hylkytavara tuotiin Europpaan.
Etu-Intian eteläpään asukkaista Polo kertoo, että he olivat tummaihoisia, mutta heidän joukossaan oli myös joku määrä juutalaisia ja nestoriolaisia kristittyjä. Brasilipuuta (erästä väripuuta), inkevääriä, pippuria ja indigoa oli siellä kosolta. Sinne saapui kauppiaita sekä Kiinasta että Länsimailta, vaikka satamat olivatkin huonot, ja ne tekivät siellä hyviä kauppoja.
Kublai kaanin laivasto sitten purjehti Etu-Intian länsirantaa seuraillen pohjoiseen päin. Pohjantähti alkoi jälleen kohota yhä korkeammalle taivaalle. Melibarin ja Gozuratin maat harjottivat merirosvoutta. Vuosittain kummastakin valtakunnasta lähti liikkeelle satakunta laivaa, jotka liittyivät yhteen pieniksi laivastoiksi ja ryöstivät kaikki kauppalaivat, mitä kiinni saivat. Kauppiaat olivat sen vuoksi ruvenneet käyttämään suuria asestettuja laivoja. Semmoiset laivat, jotka kärsivät niillä rannoilla haaksirikon, ryöstettiin armotta, mutta semmoiset, jotka satamiin saapuivat, otettiin juhlallisesti vastaan. — Indus virran suistamossa olevista maista tuotiin varsinkin pumpulia, puuvillaa ja savusteita, indigoa, hevosia ja hyvin valmistettuja nahkoja. Muita Intian merkillisyyksiä olivat »Miesten saari» ja »Naisten saari», edellisessä asujina paljaita miehiä, jälkimäisessä naisia. Kaikki asukkaat oli kristinuskoon kastettu, vaikka elivät Vanhan testamentin mukaan. Heidän ainoa päämiehensä oli piispa, joka taas oli Sokotran piispan vallan alainen. Joka vuosi miehet maaliskuun alussa lähtivät kolmenkymmenen penikulman päässä olevaan naisten saareen ja viipyivät siellä vaimojensa luona toukokuun loppuun, jolloin he taas palasivat omaan saareensa, eläen siellä loput vuotta maata viljellen ja kalastaen. Naisilla ei ollut muuta työtä kuin kasvattaa lapsiaan ja hoitaa saarensa hedelmäpuistoja. Tämä juttu oli ikivanha satuaihe, joka aikain kuluessa oli saanut uuden muodon.
Luultavasti matka kulki edelleen pitkin Mekranin ja Persian rantaa Ormuziin, mutta sen nojalla, mitä Marco Polo matkalla kuuli, hän kertoo tietoja etäisistä etelän maista, joissa hän tuskin lienee käynyt.