Hubungan antara Australia dengan Indonesia sebenarnya sudah terjalin sebelum kedatangan bangsa Barat, ketika masa kerajaan Bugis-Makasar. Pada abad ke-17 masyarakat di wilayah Bugis dan Makasar telah melakukan pelayaran ke berbagai penjuru perairan dunia hingga sampai ke benua Australia bagian Utara. Hubungan yang terjalin adalah perdagangan tradisional dengan sistem barter dan melalui alat penukar barang sederhana. Secara geografis sendiri Australia adalah sebuah benua tetangga Indonesia di sebelah selatan, dengan ini tidak diragukan lagi bahwa hubungan antara Australia dengan Indonesia memang sudah terjalin sejak zaman dahulu kurang lebih pada tahun 1650-an dengan bukti ditemukannya dapur sampah (kyoken modinger), Rumah Panggung dengan corak kebudayaan Indonesia, dan pohon asam di pesisir utara benua Australia. Selain itu adanya kemiripan bahasa yang digunakan oleh suku aborigin dengan dialeg orang bugis juga sebagai bukti hubungan tersebut.
Hubungan Indonesia dengan Australia terjalin baik sebelum perang kemerdekaan Indonesia. Orang-orang Australia mendukung konsep kebebasan bagi tiap-tiap Negara. Berita Proklamasi kemerdekaan Indonesia juga dirayakan dengan meriah di Australia oleh orang-orang Indonesia yang tinggal disana. Pada saat Belanda kembali ingin menguasai Indonesia setelah proklamasi kemerdekaan, Australia menutup pelabuhannya untuk kapal-kapal belanda. Para buruh pelabuhan memblokir kapal-kapal belanda yang berlabuh di dermaga-dermaga Australia sebagai bentuk penolakan pendudukan kembali Belanda atas Indonesia. Saat Indonesia dan Belanda mengalami konflik, Australia menjadi penengah dalam penyelesaian konflik itu.
Hubungan antara Australia dengan Indonesia selalu mengalami fluktuasi, hal ini dipengaruhi oleh beberapa faktor. Diantaranya masalah Politik, Ekonomi, Sosial-Budaya, maupun pertahanan dan keamanan masing-masing negara. Semula hubungan antara Australia – Indonesia berjalan lancar sampai pasca Perang Dunia II pada tahun 1949 pasang surut antara Australia – Indonesia mulai terjadi. Beberapa Masalah yang menyebabkan terjadinya fluktuasi hubungan Australia-Indonesia adalah:
1. Masalah Irian Barat
Terjadi perbedaan pendapat tentang Irian Barat antara Indonesia dan Australia. Belanda dalam KMB menyebutkan bahwa mengakui kemerdekaan RIS namun tanpa Irian Barat. Hatta mengatakan bahwa Indonesia tidak akan lengkap tanpa Irian Barat. Menurut Yamin, Indonesia tidak lengkap tanpa Sabah, Irian barat, dan Papua Nugini. Australia menganggap kalau Irian Barat buka bagian dari Indonesia, karena perbedaan ras (Indonesia umumnya: melanosoid, Irian Barat: Negroid) dan budaya. Pendapat Yamin dianggap Australia bahwa Indonesia adalah Negara Ekspansionis, karena mengklaim wilayah dari daerah lain.
A.H Nasution mendapat perintah untuk mencari bantuan Senjata untuk melawan Belanda dalam Agresi Militer. A.H. Nasution mendatangi Amerika namun ditolak. A.H.Nasution selanjutnya meminta bantuan ke Rusia dan diterima dengan baik. Kerjasama ini menyebabkan hubungan Indonesia dengan Rusia menjadi dekat dan pengaruh komunis masuk dan tumbuh subur di Indonesia. Autralia menganggap Indonesia merupakan ancaman Komunis yang berasal dari utara yang bisa mengganggu kestabilan politik negaranya.
2. Konfrontasi dengan Malaysia
Ide Teunku Abdulrahman (PM Malaysia) untuk membentuk Negara federasi Malaysia yang beranggotakan Malaysia, Singapora, Brunai Darusalam dianggap sebagai ancaman untuk Indonesia. Soekarno yang anti barat dan cenderung ke Komunis menganggap pembentukan federasi ini hanyalah akal-akalan Inggris untuk membangun new kolonialisme di Asia Tenggara. Inggris hanya ingin mengganggu kedaulatan Negara-negara di Asia tenggara dengan membentuk federasi itu. Menanggapi masalah ini Australia cenderung memihak ke Malaysia dengan alasan Indonesia hanya ingin mengekspansi Malaysia dengan menolak pembentukan federasi dan supaya paham komunis dapat menyebar dengan cepat ke utara. Namun yang menjadi alasan mendasar kenapa Australia mendukung Malaysia karena mereka masih sama-sama negar dibawah Britania Raya.
3. Masalah Timor-Timor
Timor-timor adalah Negara jajahan milik Poertugal. Pada masa rezim Salasar berkuasa di Portugal, wilayah ini dianggap sebagai overseas of Portugal, yaitu Negara Portugal yang ada di seberang laut sejak 400tahun yang lalu. Tahun 1974 di Portugal terjadi kudeta yang dipimpin oleh Jenderal De Spinola. Spinola memberi kebebasan kepada Timor-Timor untuk menentukan nasip sendiri. Dari situ maka Timor-Timor terbentuk 5 partai:
ª UDT, memilih ingin masuk ke Australia namun akhirnya memilih bergabung dengan Indoensia.
ª FRETILIN, merupakan partai komunis Timor-timor yang lebih menginginkan Timor-Timor untuk independent dan menjadi Negara sendiri.
ª APODETI, ingin bergabung dengan Indonesia
ª KOTA, memilih ingin tetap bergabung dengan Portugal
ª TRABALISTA, ingin bergabung dengan Portugal tapi akhirnya memilih untuk bergabung dengan Indonesia.
Menanggapi hasil dari jajak pendapat parpol yang dibentuk, maka Indonesia mengirim Tomodok (orang timor) untuk menyelidiki keadaan rakyat timor-timor. Dari penyelidikan itu disimpulkan bahwa orang-orang timor-timor ingin bergabung dengan Indonesia. Indonesia menerima baik hasil jajak pendapat itu. Kejadian ini ditentang Australia dan Indonesia kembali dianggap sebagai Negara ekspansionis.
Timor-timor resmi masuk menjadi propinsi ke-27 indonesia pada tahun 1976. Tahun 1978, Malcom Flaser (PM Australia) mengakui masuknya timor-timor ke Indonesia secara de facto. Hal ini dilakukan karena Australia mendapat tekanan dari Amerika untuk mengakui kedautalan RI, zaman ORBA Indonesia dekat dengan Amerika karena sama-sama memusuhi komunis. Saat Australia dibawah pemerintahan Bob Howke kembali mementahkan pengakuan itu, namun dalam wawancaranya dengan wartawan Indonesia saat kunjungan ke Jakarta tahun 1985 Bob Howke mengatakan bahwa dia mengakui Integrasi Timor-Timor ke Indonesia. Pada masa pemerintahan Paul Ketting hubungan Australia-Indonesia sangat baik, terbukti Indonesia menjadi Negara pertama yang mendapat kunjungan. Ini terjadi karena Kitting adalah keturunan Irlandia, dia ingin Australia merdeka penuh dan lepas dari Britania Raya.
4. Tragedy 15 November 1991
Tanggal 15 November 1991 terjadi konflik antara militer Indonesia dengan pemuda dari timor-timor yang didukung oleh Uskup Below. Sejak awal Uskup Below memang tidak suka dengan bergabungnya timor-timor ke Indonesia sebab dia adalah Uskup yang didikan Portugal. Pemuda-pemuda yang melakukan penyerangan adalah anak-anak hasil pemerkosaan militer Indonesia terhadap wanita-wanita timor-timor sehingga mereka sangat benci dengan orang-orang Indonesia. Kejadian ini dianggap oleh Australia bahwa Indonesia telah melanggar HAM.
Pada masa pemerintahan John Howart hubungan dengan Indonesia kembali memanas. John Howart meminta Amerika untuk melakukan jajak pendapat di Timor-Timor apakah masih ingin menjadi bagian dari Indonesia atau ingin membentuk Negara sendiri. ini dilakukan setelah rezim Soeharto jatuh karena gelombang reformasi. Habibie melapskan timor-timor karena dianggap tidak menguntungkan ,padalah timor-timor merupakan benteng terluar bagi Indonesia. Setelah merdeka dari Indonesia Timor-Timor bukan semakin baik, justru menjadi semakin kacau karena terajdi perang saudara.
5. Berita di Sydney Morning Herale yang memuat tentang kekayaan Soeharto
Tahun 1985, David Jenkins, wartawan Sydney Morning Herale memberitakan tentang harta dari presiden RI Soeharto.
à Kekayaan Soeharto tidak akan habis tujuh turunan
à Setiap harinya Ny. Tien Soeharto menerima uang bermilyar-milyar
à Soeharto memberikan keleluasaan pada Lim Sui Lion untuk memonopoli perekonomian Indonesia.
Masyarakat Indonesia tersinggung atas pemberitaan itu. Kunjungan menteri luar negeri Indonesia, Mochtar Kusuma Atmaja, ke Australia dibatalkan sebagai bentuk kemarahan Indonesia. Pemerintah menuntut pemerintah Australia untuk menangkap David Jenkins, namun Australia menolak karena kebebasan pers di Australia dijunjung tinggi.