Untuk melawan bangsa Mongol di Tiongkok, Kertanegara bekerja sama dengan kerajaan-kerajaan di Nusantara dan Asia Tenggara.

Sejak mendirikan Dinasti Yuan, Khubilai Khan mulai menebar kekuasannya. Ia menuntut bakti dari penguasa-penguasa yang sebelumnya mengakui kekuasaan kaisar-kaisar Dinasti Sung. Jika menolak, mereka akan diserang. Salah satunya penguasa di Jawa.

Khubilai Khan mengirim utusan ke Jawa pada 1280, 1282, dan 1286. Raja Singhasari, Kertanegara dengan percaya diri merusak muka utusan terakhir, Meng Qi pada 1289, karena telah menjalin hubungan baik dengan kerajaan-kerajaan lain di Nusantara dan Asia Tenggara.

Sebagaimana disebut dalam Kakimpoi Nagarakrtagama, bahwa seluruh Jawa, Sunda, dan Madura tunduk di bawah kekuasaan Kertanegara. Ia mengirim ekspedisi militer ke Malayu, menguasai Pahang di Semenanjung Malayu, serta menaklukkan Bali dan memboyong rajanya sebagai tawanan pada 1284. Ia juga menguasai Gurun, pulau di wilayah timur Nusantara, dan Bakulapura atau Tanjungpura di barat daya Kalimantan.

Dalam Prasasti Camundi dari 1292 disebutkan Kertanegara puas dengan kemenangan-kemenangannya di semua tempat. Ia menjadi payung pelindung seluruh Dwipantara atau Nusantara.

Sejarawan Malang, Suwardono dalam Kertanegara dan Misteri Candi Jawi, menjelaskan Prasasti Camundimemberikan petunjuk tentang hubungan Kertanegara dengan kawasan Asia Tenggara bagian selatan dan kepulauan. Itu pula yang dimaksud dalam Nagarakrtagama.

Menurut Dwi Cahyono, arkeolog dan pengajar sejarah di Universitas Negeri Malang, walaupun dalam Nagarakrtagama disebut menundukkan bukan berarti ada pertempuran. "Kalau ada (pertempuran) itu akan mempermudah Mongol masuk, karena energi berkurang," ujarnya.

Khususnya ekspedisi ke Malayu pada 1275. Untuk mempererat hubungan dengan Malayu, pada 1286 Kertanegara mengirimkan hadiah berupa arca Buddha Amoghapasa. Penempatannya di Dharmasraya dipimpin oleh empat pejabat tinggi dari Jawa.

Menurut Dwi itu bukan ekspedisi militer melainkan untuk merekut mitra sejajar. "Menurut saya ini semacam MoU (memorandum of understanding). Jika dua kekuatan itu berkoalisi, diharapkan dapat mengontrol Selat Malaka dan menghadapi musuh bersama, khususnya menghadapi serangan Mongol," kata Dwi.

Selain di kawasan Nusantara, Kertanegara juga bersekutu dengan Kerajaan Champa. Tujuannya sama: untuk membendung serangan bangsa Tartar, sebutan Jawa untuk Mongol.

Dalam Prasasti Po Sahdi dekat Phanrang dari 1306 disebutkan seorang permaisuri Raja Champa adalah putri dari Jawa bernama Tapasi. Adik Kertanegara itu menikah dengan Raja Jaya Simhawarman III (1287-1307).

Kerja sama itu menguntungkan bagi Jawa ketika Kubilai Khan mengirim pasukan pada 1292 untuk menghukum Kertanegara. Raja Jaya Singhawarman III tidak mengizinkan mereka menurunkan jangkar di pelabuhan Champa untuk mengisi perbekalan. Apalagi selama berlayar ke Jawa, mereka menghadapi banyak kesulitan.

Shi Bi, salah satu komandan ekspedisi dalam catatannya di Sejarah Dinasti Yuan, menyebut angin selama pelayaran bertiup sangat kencang. Lautan begitu bergelombang membuat kapal terombang-ambing. Para prajurit pun tak makan selama berhari-hari.

Ditambah lagi, menurut W.P. Groeneveldt dalam Nusantara dalam Catatan Tionghoa, armada Mongol yang berlayar dari Quanzhou di Fujian itu tidak mengikuti rute biasanya yang menyusuri pesisir Malaka dan Sumatra. Mereka justru berlayar di tengah lautan dan dengan berani atau mungkin nekat mengambil rute lurus terdekat menuju tujuannya.

Akibatnya, dari ribuan kapal, yang berhasil sampai Jawa Timur hanya sebagian kecilnya. Banyak yang tewas. Baik karena serangan bajak laut, maupun penyakit. "Mongol itu tidak jago berlayar. Apalagi paling sulit melintasi Laut Cina Selatan," kata Dwi.

Banyak yang yakin ekspedisi Khubilai Khan ke Jawa sebenarnya demi menguasai perdagangan laut. Namun, David W. Bade, ahli perpustakaan di Joseph Regenstein Library Universitas Chicago, dalam Of Palm Wine, Women and War: The Mongolian Naval Expedition to Java in the 13th Century, menjelaskan bahwa saat itu Jawa menjadi negara terakhir di selatan Tiongkok yang menolak tunduk. Pengaruh Jawa semakin besar setelah mengirim utusan ke Malayu dalam ekspedisi Pamalayu. Apalagi pengaruh Sriwijaya, yang berhubungan baik dengan Tiongkok, sudah pudar.

"Kemungkinan invasi Mongol ke Jawa hanya karena hasrat Khubilai Khan mengirimkan angkatan lautnya dan juga amarahnya setelah Meng Qi dilukai, masih terus dipertanyakan," tulis Bade.

Morris Rossabi, sejarawan Queens College dan Columbia University, salah satu yang meragukan ekspedisi Mongol ke Jawa hanya untuk menghukum orang asing yang melukai utusannya. "Sementara banyak sekali yang harus dipertaruhkan dalam ekspedisi ini," tulis Rossabi dalam Khubilai Khan: His Life and Times.

Jika dilihat secara umum, menurut Groeneveldt, penguasa di Tiongkok selalu digerakkan oleh karakter superioritas mereka. Kala itu, supremasi Tiongkok terhadap negara-negara lain adalah dogma nasional yang begitu tertanam, bahwa kaisar ditunjuk Langit untuk menjadi penguasa dunia.

Sejak masa awal sejarah Tiongkok, mereka selalu mencatat kedatangan penguasa asing yang memberikan penghormatan kepada kaisar. Para penguasa dari negara-negara yang lebih kecil di Asia sering melakukan perdagangan hingga ke Tiongkok, sambil membawa hadiah untuk mengambil hati penguasanya. Bahkan, cara ini diikuti para pedagang swasta yang menyamar sebagai utusan dari negeri jauh. Dengan memberikan sedikit barang dagangan, mereka berharap mendapat fasilitas perdagangan atau akses hingga ke ibu kota.

"Keuntungan utama hubungan ini adalah kesempatan bagi para penguasa di negara-negara lain agar bisa berdagang di Tiongkok," tulis Groeneveldt.

Sejak dulu Tiongkok dipandang tinggi, khususnya oleh negara-negara di Asia. Budayanya tinggi, istananya mewah dan luas. Kekayannya membuat kagum bangsa-bangsa di Asia. Karenanya para penguasa merasa mendapat kehormatan jika bisa menjalin hubungan dengan Tiongkok.

Sementara bagi kaisar, semua negara harus tunduk kepada bangsa yang dipilih Langit, yaitu Tiongkok. Jika ada yang memberikan hadiah (upeti), walaupun sedikit harus diterima dengan tangan terbuka dan dibantu sesuai dengan kebutuhannya.

"Bangsa Tionghoa bahkan menjadikan upaya kontak dagang biasa menjadi pengakuan atas superioritas mereka," tulis Groeneveldt.

Terlebih lagi kekuasaan Tiongkok di era Dinasti Mongol. Menurut sejarawan Inggris, John Man dalam Kubilai Khan, ambisi utama Sang Khan adalah membuat dunia mengakui kejayaannya. "Tak ada alasan khusus kenapa harus menaklukkan suatu negara. Ia hanya harus melakukannya," tulis John Man.

Oleh karena itu, menurut Suwardono, Kertanegara berusaha untuk menyatukan seluruh Nusantara karena adanya bahaya dari luar yang mengancam, yaitu pasukan Mongol.