Bandar Udara Internasional Melbourne
yang berada di luar terminal. Pengerjaan dimulai di bangunan enam lantai Hilton Hotel (sekarang Park Royal) dengan 276 kamar di atas parkir mobil pada Januari 1999, yang selesai pada pertengahan tahun 2000 dengan biaya $55 juta. Pengembangan terminal domestik Qantas selesai pada tahun 1999, menyediakan demaga kedua dan 9 tempat parkir pesawat tambahan.
Pada bulan Desember 2000 terminal penumpang keempat dibuka: Terminal Domestik Express, yang berlokasi di sebelah selatan bangunan termina utama dengan biaya $9 juta. Ini merupakan bangunana terminal penumpang tambahan pertama di Bandar Udara Internasional sejak tahun 1971.
Pengembangan parkir mobil juga dilanjutkan dengan proyek senilai $40 juta yang dimulai pada tahun 2004, melipatgandakan ukuran parkir mobil jangka pendek dengan penambahan 2500 ruang di atas enam lantai, bersama dengan 1200 ruang baru yang ditambahkan pada 500 tempat yang sudah ada di ruang parkir jangka panjang. Pendapatan dari operasi ritel di Bandara Melbourne menembus batas $100 juta untuk pertama kali pada tahun 2004, yang menjadi peningaktan senilai 100% dibandingkan dengan tahun pertama privatisasi.
Pelebaran landasan pacu utama selebar 15 meter selesai dalam pengerjaan 29 hari pada bulan Mei 2005, yang memungkinkan pengoperasian Airbus A380. Pengerjaan dilanjutkan pada Maret 2006 dengan pengembangan terminal 2 seluas 5.000 m dan penambahan lantai di ruang tunggu bandara di atas terminal. Pada tahun 2008 perluasan Terminal 2 seluas 25000 m senilai $330 juta dimulai yang selesai pada tahun 2011. Pengerjaan
meliputi 5 garbarata tambahan di kumpulan terminal penumpang baru, dan penambahan 5.000 m wilayah pengamanan luar dan bea cukai.
Terminal Bandar Udara Melbourne memiliki 56 gerbang: 40 domestik dan 16 internasional. Terdapat lima posisi parkir khusus kargo di Apron Kargo Selatan. Sistem penomoran terminal saat ini diperkenalkan pada Juli 2005; Terminal tersebut sebelumnya dikenal sebagai Qantas Domestic, International, dan Selatan (sebelumnya Ansett Domestic).
Terminal 1 menangani layanan domestik bagi maskapai Qantas Group, Qantas, Jetstar dan QantasLink dan berlokasi di ujung utara bangunan. Keberangkatan berlokasi di lantai pertama, sedangkan kedatangan berlokasi di lantai dasar. Terminal memiliki 16 ruang parkir yang dilengkapi dengan garbarata; 12 dilengkapi dengan garbarata tunggal sedangkan empat yang lain dengan garbarata ganda. Terdapat lima gerbang tanpa garbarata, yang digunakan oleh QantasLink dan Jetstar.
Dibuka bersama dengan Baandar Udara Melbourne pada tahun 1970 untuk Trans Australia Airlines, terminal diberikan kepada Qantas pada tahun 1992 saat mereka membeli maskapai tersebut. Pengerjaan pengembangan terminal asli dimulai pada Oktober 1997 dan selesai pada akhir tahun 1999 dengan biaya $50 juta, dilengkapi dengan dermaga kedua, ruang tambahan untuk 9 pesawat, perpanjangan jalan akses, dan pengembangan keseluruhan terminal.
Saat ini, sejumlah besar toko dan otlet makanan terletak di bagian ujung terminal di dekat pintu masuk menuju Terminal 2. Qantas memiliki sebuah Qantas Club, ruang tunggu Kelas Bisnis dan Pemilik Perusahaan di terminal.
Terminal 2 menangani semua penerbangan internasional yang keluar dari Bandar Udara Melbourne dan dibuka bersama dengan pembukaan bandara pada tahun 1970. Terminal memiliki 16 gerbang dengan garbarata (meskipun gerbang 18 dan 20 belum selesai dipasang). Terminal juga memiliki 2 gerbang tanpa garbarata. Cathay Pacific, Malaysia Airlines, Qantas (termasuk dua ruang tunggu di Terminal 2, Ruang tunggu Utama dan Bisnis/Qantas Club), Singapore Airlines, Air New Zealand/United Airlines dan Emirates Airline mengoperasikan ruang tunggu maskapai di terminal ini.
Di terminal internasional terdapat karya seni hasil dari seniman pribumi Australia termasuk Daisy Jugadai Napaltjarri dan Gloria Petyarre.
Progam pengembangan senilai $330 juta untuk Terminal 2 diumumkan pada tahun 2007. Target proyek ini meliputi ruang tunggu baru dan fasilitas ritel, sebuah terminal satelit baru, menngkatkan kapasitas bagasi, dan perancangan ulang wilayah keamanan dan bea cukai. Terminal satelit baru dilengkapi dengan jendela kaca hingga mencapai lantai yang menawarkan pemandangan dari landasan pacu
Utara-Selatan. Kumpulan baru meliputi tiga garbarata ganda, yang masing-masing dapat menampung sebuah pesawat A380 atau dua pesawat yang lebih kecil dengan garbarata tunggal. Kemampuan penanganan bagasi akan ditingkatkan, dan dua korsel bagasi bari akan ditambahkan untuk menghadapi peningkatan lalu lintas A380. Pengerjaan dimulai pada November 2007 dan akan selesai pada tahun 2011.
Meskipun disebutkan sebagai terminal satelit, bangunan terminal dihubungkan dengan koridor di atas lantai dengan Terminal 2. Keberangkatan dilakukan di lantai dasar (sejajar dengan ruang tunggu keberangkatan A380 yang digunakan di Gerbang 9 dan 11), dengan kedatangan diarahkan di lantai pertama untuk dihubungkan dengan lantai kedatangan lantai pertama saat ini. Semua gerbang kecuali gerbang 18 dan 20 saat ini menangani penumpang.
Terminal 3- dibuka bersama dengan pembukaan bandara sebagai terminal Ansett Australia terminal, namun sekarang dimiliki oleh Bandar Udara Melbourne. Terminal 3 merupakan basis dari Virgin Australia dan Regional Express Airlines. Saat ini terminal dilengkapi dengan sebelas posisi pakir yang dilengkapi garbarata dan delapan posisi parkir tanpa garbarata.
Sebuah pengembangan di terminal disetujui pada tahun 1989 dan selesai pada tahun 1991 saat dermaga kedua ditambahkan oleh Ansett di sebelah selatan untuk digunakan oleh maskapai penrbangan regional yang lebih kecil Kendell. Terminal ini digunakan secara eksklusif oleh Ansett Group untuk penerbangan domestiknya hingga kebangkrutanya pada 2001. Direncakanan akan digunakan oleh Ansett "Baru", di
bawah kepemilikan Tesna- namun setelah pengunduran diri Tesna Group dari usaha pembelian Ansett pada tahun 2002, terminal dijual kembali ke Bandar Udara Melbourne oleh administrator Ansett. Setelah itu, Bandar Udara Melbourne melakukan renovasi besar dan memperindah terminal, dikuti dengan kepindahan Virgin Australia (sebelumnya Virgin Blue) dari tempat yag kemudian disebut sebagai Domestic Express (sekarang Terminal 4), dan sejak saat itu
mengoperasikan ruang tunggu di terminal, menggunakan bekas wilayah ruang tunggu Ansett Australia Golden Wing. Regional Express juga mengoperasikan ruang tunggu maskapai di terminal ini.
Terminal 4- pada awalnya disebut Domestic Express atau Terminal Selatan- dibangun untuk maskapai bertarif rendah dan fasilitas pertama jenis ini yang ada di bandara konvensional di Australia. Pada awalnya dibangun untuk Virgin Blue (Virgin Australia) dan Impulse Airlines. Virgin Blue kemudian berpindah ke Terminal 3 setelah penutupan Ansett. Renovasi senilai $5 juta dimulai pada Juni 2007 mengikuti trend model terminal bertarif rendah di Bandar Udara Singapura Changi
dan Bandar Udara Internasional Kuala Lumpur. Biaya pendaratan dan penanganan bandara yang lebih rendah kepada bandara dapat dilakukan karena fasilitas dasar, tidak adanya garbarata, dan fasilitas dan otlet ritel yang lebih sedikit dibandingkan dengan terminal konvensional. Namun, terminal ini diletakkan di sebelah bangunan terminal utama, tidak seperti di Singapura dan Kuala Lumpur. Terminal ini dibangun
kembali oleh Tiger Airways Australia, yang menggunakannya sebagai hub utama sejak mengoperasikan penerbangan domestik pertamanya pada 23 November 2007.
Jetstar Airways memastikan keterlibatannya dalam diskusi degan Bandar Udara Melbourne mengenai pengembangan fasilitas terminal untuk mengakmodir pertumbuhan layanan bertarif rendah. Rencana pengambangan Terminal 4 meliputi insfrastruktur untuk mengakomodir penerbangan Tiger Airways Australia dan Jetstar Airways. Rencana tersebut masih dalam pengembangan, dan pengambangan dari Terminal 4 akan meliputi relokasi pusat kargo saat ini. Jika disetujui,