La flotta, lasciato Coilum, seguì verso il nord la costa del Malabar, e giunse sulle sponde del reame di Ely, che sembra corrispondere a Mangalore, nell'antico regno di Samorin. «Qui, dice il Veneziano, nasce pepe, giengiavo ( ginepro ) e molte altre ispezierie.»
Al nord di quel regno stendevasi quella contrada che il viaggiatore veneziano chiama Melibar, e che è situata al nord del Malabar propriamente detto. Le navi dei negozianti del Mangi venivano spesso a trafficare cogli indigeni di questa parte dell'India, che loro fornivano carichi di droghe eccellenti, bugrani preziosi ed altre mercanzie di gran valore; ma i loro vascelli erano troppo sovente saccheggiati dai pirati della costa, che avevano fama di terribili uomini di mare. Quei pirati abitavano più particolarmente la penisola di Gohurat, oggi Gudgiarate, verso la quale la flottiglia si diresse dopo aver veduto Tanat, contrada ove si raccoglie l'incenso bruno, Kambaget, città che fa gran traffico di cuoio. Visitato che ebbero Sumenat, città della penisola, i cui abitanti sono idolatri, crudeli e feroci, e poi Kesmacoram, probabilmente l'attuale Kedge, ultima città delle Indie tra occidente e settentrione, Marco Polo, in luogo di risalire verso la Persia, ove l'attendeva il fidanzato della principessa tartara, s'inoltrò verso occidente, traverso il vasto mare d'Oman.
La sua insaziabile passione d'esploratore lo trascinò così per cinquecento miglia sino alle rive dell'Arabia, ove gettò l'áncora alle isole Maschio e Femmina, così chiamate perchè una è unicamente abitata da uomini, l'altra da donne, che vengono visitate da quelli durante i mesi di marzo, aprile e maggio. «Questi uomini, dice il nostro esploratore, sono cristiani battezzati e non hanno signore, salvo che hanno un vescovo ch'è sotto l'arcivescovo di Scara.» Lasciate quelle isolette, la flotta fece vela a mezzodì verso l'isola di Scara, ch'è veramente Socotora, l'antica Dioscorides Insula dei Greci, ch'è posta all'ingresso del golfo d'Aden, e di cui Marco Polo riconobbe diverse parti. Egli parla degli abitanti di Socotora come di abili incantatori, che con le loro arti ottengono quanto vogliono e comandano agli uragani ed alle tempeste. Poi, discendendo ancora di miglio in miglio verso il sud, spinse la sua flotta sino alle coste del Madagascar.
Agli occhi del nostro viaggiatore, Madagascar è una delle più grandi e più nobili isole del mondo, d'un circuito di ben quattromila miglia. Gli abitanti sono per la maggior parte maomettani, e vivono sotto la signoria di dodici governatori. Sono molto dediti al commercio, e particolarmente al traffico dei denti di elefanti e dell'ambra. Si nutrono specialmente di carne di cammello, che è migliore e più sana di qualsiasi altra. I negozianti che vengono dalle coste dell'India non impiegano più di venti giorni a traversare il mar d'Oman; ma nel ritorno ci spendono non meno di tre mesi, in causa delle correnti contrarie che tendono sempre a respingerli verso il sud. Nondimeno, frequentano quell'isola perchè fornisce loro il legno di sandalo, di cui sonvi intere foreste, e l'ambra, ch'essi scambiano con drappi d'oro e di seta, con grande guadagno e profitto. Secondo Marco Polo, non mancano in quel reame le fiere e la cacciagione: leopardi, leoni, orsi, cervi, cinghiali, giraffe, asini selvaggi, caprioli, daini, bestie da pascolo vi si incontrano a mandre numerose; ma ciò che gli parve meraviglioso fu l'uccello grifone, ossia il roc, di cui si parla tanto nelle Mille ed una notte. «Questi uccelli, dic'egli, non sono fatti com'e' si dice di qua, cioè mezzo uccello e mezzo lione, ma sono fatti come aguglie ( aquile ) e sono capaci di sollevare un elefante negli artigli.» Quest'uccello meraviglioso è probabilmente l' epyornis maximus, di cui si trovano ancora delle uova al Madagascar.
Da quell'isola Marco Polo, risalendo verso il nord-ovest, venne a riconoscere Zanzibar e la costa africana, ch'egli prese per un'isola. Gli abitanti gli sembrarono smisuratamente robusti e capaci di portare il carico di quattro uomini, «e questo non è maraviglia, chè mangia l'uno bene per cinque persone.» Quegli indigeni erano negri e camminavano nudi; avevano la bocca grande, il naso «rabbuffato in suso,» le labbra e gli occhi grossi; descrizione esattissima, che s'adatta ancora ai naturali di quella parte dell'Africa. Quegli Africani vivono di riso, latte, carne e datteri, e fabbricano il vino con riso, zuccaro e droghe. Sono valenti guerrieri, nè temono la morte; combattono sopra cammelli o elefanti, armati di scudi di cuojo, di spade e di lancie, ed eccitano le loro cavalcature inebbriandole di bevande spiritose. «Qui, soggiunge il nostro viaggiatore, si hanno le più sozze femmine del mondo, ch'elle hanno la bocca grande, e il naso grosso e corto, e le mani grosse quattro cotanti che l'altre.»
Ai tempi di Marco Polo, secondo l'osservazione del Charton, i paesi compresi sotto la denominazione d'India si dividevano in tre parti: l'India Maggiore, cioè l'Indostan e tutto il paese posto fra il Gange e l'Indo; l'India Minore, cioè la contrada al di là del Gange, dalla costa occidentale della penisola fino alla costa della Cocincina; finalmente l'India Media, cioè l'Abissinia e le rive arabe fino al golfo Persico.
Lasciando Zanzibar, Marco Polo si diresse verso quest'India Media, ch'egli chiama Nabasce ( Abissinia ), risalendo verso il nord ed esplorando il litorale di quel paese fertilissimo. «Nabasce, dice il nostro viaggiatore, è una grandissima provincia; e sappiate che 'l maggiore re di questa provincia si è cristiano, e tutti gli altri re della provincia sono sottoposti a lui, i quali sono sei re, tre cristiani e tre saracini. Il re maggiore dimora nel mezzo della provincia, e i saracini dimorano verso Edenti ( Aden ), nella quale contrada messer San Tomaso convertì molta gente, poscia se ne partío, e andonne a Nabar, colà dove fu morto.» Parlando della vita degli abitanti e della fauna del paese, dice che «la vita loro si è riso e carne, e hanno leonfanti, e non ch'egli vi naschino, ma vengono d'altri paesi. Nasconvi molte giraffe e molte altre bestie, e hanno molte bellissime galline, e sì hanno istruzzoli ( struzzi ) grandi come asini, o poco meno; e sì hanno molte altre cose, ch'a volerle tutte contare sarebbe troppo lunga mena. Cacciagioni e uccellagioni si hanno assai, e si hanno pappagalli bellissimi e di più fatte, e si hanno gatti mamoni e iscimmie assai.»
Lasciato il litorale dell'Abissinia, la flotta toccò Edenti, la moderna Aden, vicino all'imboccatura del Mar Rosso. Aden era a quel tempo una città importantissima pel traffico dell'Oriente, e nel suo porto convenivano tutti i navigli che commerciavano coll'India e colla China. La flotta visitò quindi Icier (la moderna Schehr nell'Hadzamauth, sulla costa meridionale dell'Arabia), «grande città, dice il Veneziano, la quale è sotto il soldano d'Edenti ed ha un porto eccellente, al quale càpitano molte navi, le quali vengono dall'India con molta mercatanzia;» Dufar (Dafur, sulla costa arabica meridionale), che produce un incenso di prima qualità; Chalatu (Kalhat, sulla costa arabica orientale), «città posta sulla bocca del golfo di Chalatu, sì che veruna nave vi può passare nè usare senza la volontà di questa città;» e per ultimo Curmaso (Hormuz), che Marco Polo aveva già visitata, quando da Venezia si recò alla corte del re tartaro.
È a quel porto del golfo Persico che terminò la traversata della flotta allestita dall'imperatore mongollo. La principessa era finalmente giunta ai confini della Persia, dopo una navigazione che aveva durato non meno di diciotto mesi. Ma nel frattempo il principe Arghum, suo fidanzato, era morto, ed il regno era straziato dalla guerra civile. La principessa fu dunque consegnata al figlio d'Arghum, il principe Ghazan, che salì al trono nel 1295, dopo che l'usurpatore, fratello d'Arghum, fu strangolato. Non si sa che avvenisse della principessa; ma prima di separarsi da Marco, Matteo e Niccolò Polo, ella lasciò loro segni dell'alto favore in cui li teneva.
Fu probabilmente durante il suo soggiorno in Persia che Marco Polo raccolse documenti interessanti sulla Gran Turchia; sono documenti staccati ch'egli dà al termine della sua relazione, vera storia dei kan mongolli della Persia. Ma i suoi viaggi d'esplorazione erano terminati. Preso commiato dalla principessa tartara, i tre Veneziani, bene scortati, presero la via di terra per tornare in patria. Si recarono a Trebisonda e Costantinopoli, da Costantinopoli a Negroponte, ed ivi s'imbarcarono per Venezia.