Persengketaan antara Indonesia dengan Malaysia, mencuat pada tahun 1967 ketika dalam pertemuan teknis hukum laut antara kedua negara, masing-masing negara ternyata memasukkan pulau Sipadan dan pulau Ligitan ke dalam batas-batas wilayahnya. Kedua negara lalu sepakat agar Sipadan dan Ligitan dinyatakan dalam keadaan status status quo akan tetapi ternyata pengertian ini berbeda. Pihak Malaysia membangun resor pariwisata baru yang dikelola pihak swasta Malaysia karena Malaysia memahami status quo sebagai tetap berada di bawah Malaysia sampai persengketaan selesai, sedangkan pihak Indonesia mengartikan bahwa dalam status ini berarti status kedua pulau tadi tidak boleh ditempati/diduduki sampai persoalan atas kepemilikan dua pulau ini selesai. Sedangkan Malaysia malah membangun resort di sana Sipadan dan Ligitan tiba-tiba menjadi berita, awal bulan lalu. Ini, gara-gara di dua pulau kecil yang terletak di Laut Sulawesi itu dibangun cottage. Di atas Sipadan, pulau yang luasnya hanya 4 km2 itu, siap menanti wisatawan. Pengusaha Malaysia telah menambah jumlah penginapan menjadi hampir 20 buah. Dari jumlahnya, fasilitas pariwisata itu memang belum bisa disebut memadai. Tapi pemerintah Indonesia, yang juga merasa memiliki pulau-pulau itu, segera mengirim protes ke Kuala Lumpur meminta agar pembangunan di sana dihentikan terlebih dahulu. Alasannya, Sipadan dan Ligitan itu masih dalam sengketa, belum diputus siapa pemiliknya. Pada tahun 1969 pihak Malaysia secara sepihak memasukkan kedua pulau tersebut ke dalam peta nasionalnya.
Pada tahun 1976, Traktat Persahabatan dan Kerja Sama di Asia Tenggara atau TAC (Treaty of Amity and Cooperation in Southeast Asia) dalam KTT pertama ASEAN di pulau Bali ini antara lain menyebutkan bahwa akan membentuk Dewan Tinggi ASEAN untuk menyelesaikan perselisihan yang terjadi di antara sesama anggota ASEAN akan tetapi pihak Malaysia menolak beralasan karena terlibat pula sengketa dengan Singapura untuk klaim pulau Batu Puteh, sengketa kepemilikan Sabah dengan Filipina serta sengketa kepulauan Spratly di Laut Cina Selatan dengan Brunei Darussalam, Filipina, Vietnam, Cina, dan Taiwan. Pihak Malaysia pada tahun 1991 lalu menempatkan sepasukan polisi hutan (setara Brimob) melakukan pengusiran semua warga negara Indonesia serta meminta pihak Indonesia untuk mencabut klaim atas kedua pulau.
Sikap pihak Indonesia yang ingin membawa masalah ini melalui Dewan Tinggi ASEAN dan selalu menolak membawa masalah ini ke ICJ kemudian melunak. Dalam kunjungannya ke Kuala Lumpur pada tanggal 7 Oktober 1996, Presiden Soeharto akhirnya menyetujui usulan PM Mahathir tersebut yang pernah diusulkan pula oleh Mensesneg Moerdiono dan Wakil PM Anwar Ibrahim, dibuatkan kesepakatan "Final and Binding,"pada tanggal 31 Mei 1997, kedua negara menandatangani persetujuan tersebut. Indonesia meratifikasi pada tanggal 29 Desember 1997 dengan Keppres Nomor 49 Tahun 1997 demikian pula Malaysia meratifikasi pada 19 November 1997.
Keputusan Mahkamah Internasional
Pada tahun 1998 masalah sengketa Sipadan dan Ligitan dibawa ke ICJ,[1][2] kemudian pada hari Selasa 17 Desember 2002 ICJ mengeluarkan keputusan tentang kasus sengketa kedaulatan Pulau Sipadan-Ligitan antara Indonesia dengan Malaysia. Hasilnya, dalam voting di lembaga itu, Malaysia dimenangkan oleh 16 hakim, sementara hanya 1 orang yang berpihak kepada Indonesia. Dari 17 hakim itu, 15 merupakan hakim tetap dari MI, sementara satu hakim merupakan pilihan Malaysia dan satu lagi dipilih oleh Indonesia. Kemenangan Malaysia, oleh karena berdasarkan pertimbangan effectivity (tanpa memutuskan pada pertanyaan dari perairan teritorial dan batas-batas maritim), yaitu pemerintah Inggris (penjajah Malaysia) telah melakukan tindakan administratif secara nyata berupa penerbitan ordonansi perlindungan satwa burung, pungutan pajak terhadap pengumpulan telur penyu sejak tahun 1930, dan operasi mercu suar sejak 1960-an. Sementara itu, kegiatan pariwisata yang dilakukan Malaysia tidak menjadi pertimbangan, serta penolakan berdasarkan chain of title (rangkaian kepemilikan dari Sultan Sulu) akan tetapi gagal dalam menentukan batas di perbatasan laut antara Malaysia dan Indonesia di selat Makassar.[3]
^http://www.icj-cij.org/docket/files/102/7177.pdfDiarsipkan 2015-04-02 di Wayback Machine. FOR SUBMISSION TO THE INTERNATIONAL COURT OF JUSTICE OF THE DISPUTE BETWEEN INDONESIA AND MALAYSIA CONCERNING SOVEREIGNTY OVER PULAU LIGITAN AND PULAU SIPADAN, jointly notified to the Court on 2 November 1998