Dari Samudra Pasai, Ibnu Batutah mula-mula berlayar ke Bandar [[Malaka]] di [[Semenanjung Malaya]] yang ia sebut "Mul Jawi". Ia berjumpa dengan Raja Malaka, dan menginap sebagai tamu raja selama tiga hari.
Dari Malaka, Ibnu Batutah berlayar ke sebuah kerajaan bernama Kailukari di Negeri [[Tawalisi]], tempat ia berjumpa dengan [[Urduja]], seorang putri pribumi. Urduja adalah seorang pendekarsrikandi perempuan yang gagah beranipemberani, dan rakyatnya memusuhi [[dinasti Yuan|wangsa Yuan]]. Ibnu Batutah meriwayatkan bahwa Urduja adalah seorang "penyembah berhala", namun pandai menuliskan [[Basmalah|Kalimat Basmalah]] sesuai [[kaligrafi Islam|kaidah seni menyurat Islam]]. Lokasi Kailukari maupun Tawalisi masih menjadi pokok perdebatan. Kailukari mungkin saja adalah [[Po Klong Garai]] di [[Campa]] (sekarang kawasan selatan Vietnam), dan Urduja boleh jadi adalah salah seorang bangsawati Campa dari [[wangsa Trần]]. Masyarakat Filipina meyakini bahwa Kailukari adalah daerah yang kini menjadi [[Pangasinan|Provinsi Pangasinan]] di negara [[Filipina]].<ref>{{cite web|last=Balmaceda Guiterrez|first=Chit|title=In search of a Princess |url=http://www.urduja.com/princess.html|publisher=Filipinas Magazine|accessdate=26 September 2013|deadurl=no|archiveurl=https://web.archive.org/web/20130927233532/http://www.urduja.com/princess.html|archivedate=27 September 2013|df=dmy-all}}</ref> Pada zaman modern, sosok Urduja ditampilkan dalam buku-buku bacaan dan film-film Filipina sebagai salah seorang pahlawan nasional perempuan negara itu. Banyak tempat lain yang juga diperkirakan sebagai lokasi kerajaan ini, mulai dari Pulau [[Jawa]] sampai ke [[Provinsi Guangdong]] di Tiongkok. Meskipun demikian, Sir [[Henry Yule]] dan [[William Henry Scott (sejarawan)|William Henry Scott]] beranggapan bahwa seluruh riwayat tentang Negeri Tawalisi maupun Putri Urduja hanya khayalan belaka (untuk keterangan lebih lanjut, baca [[Tawalisi]]).
Dari Kailukari, Ibnu Batutah bertolak menuju Bandar [[Quanzhou]] di Provinsi [[Fujian]], Negeri Tiongkok.
