Sân bay này đã được xây xong để thay thể sân bay gần đó đã quá hạn là sân bay Essendon có đường băng và nhà ga không thể tiếp nhận các loại tàu bay lớn như Boeing 747 và McDonnell Douglas DC-10 cuối những năm 1960. Sân bay được khánh thành ngày 1/7/1970. Dân địa phương thường gọi sân bay này là "Tullamarine Airport" hay vắn tắt là 'Tulla' theo tên địa điểm đặt sân bay này. Sân bay Melbourne có 3 nhà ga hàng không. Nhà ga quốc tế T2 có 16 cổng ra tàu bay, trong đó cổng 12-16 không có ống lồng ra máy bay. Hai nhà ga quốc nọi, T1 được hãng Quantas độc quyền sử dụng và T3 được nhiều hãng sử dụng có 46 cổng giữa chúng. trong năm tài chính 2004-2005, sân bay này phục vụ 21 triệu lượt khách với 180.500 lượt máy bay cất hạ cánh, trong đó có 151.200 là quốc nội. Đây là sân bay tấp nập thứ hai của Úc, sau sân bay quốc tế Kingsfort Smith ở Sydney. Sân bay này hoạt động 24/24h. Sân bay đang được nâng cấp để cuối năm 2007 có thể tiếp nhận máy bay khổng lồ 2 tầng Airbus A380.
Nhà ga
Nhà ga số 1
Nhà ga số 1 phục vụ chuyến bay nội địa và khu vực cho các hãng hàng không của Qantas Group, Qantas và QantasLink (nằm ở đầu phía bắc của nhà ga). Chuyến đi nằm ở tầng một, trong khi chuyến đến nằm ở tầng trệt. Nhà ga có 16 cửa ra máy bay sử dụng ống lồng; 12 ống lồng đơn và 4 ống lồng đôi. Có 5 cửa khởi hành không sử dụng ống lồng được QantasLink sử dụng.
Khai trương sân bay Melbourne vào năm 1970 phục vụ cho Trans Australia Airlines, nhà ga được chuyển cho Qantas vào năm 1992 khi hãng mua lại hãng hàng không này. Công việc hoàn thiện nhà ga bắt đầu vào tháng 10 năm 1997 và hoàn thành vào cuối năm 1999 với chi phí 50 triệu đô la, bao gồm một ống lồng, thêm 9 cửa ra máy bay, đường vào mới mở rộng.
Ngày nay, một loạt các cửa hàng và ăn uống nằm ở cuối nhà ga gần lối vào Nhà ga số 2. Qantas có Qantas Club, Hạng Thương gia và phòng chờ dành cho chủ tịch trong nhà ga.
Nhà ga số 2
Nhà ga số 2 phục vụ tất cả các chuyến bay quốc tế và một số chuyến bay nội địa ra khỏi Sân bay Melbourne, được khai trương vào năm 1970. Nhà ga có 20 cửa ra máy bay sử dụng ống lồng. Cathay Pacific, Qantas (bao gồm hai phòng chờ ở Nhà ga số 2, phòng chờ hạng Nhất và phòng chờ hạng Thương gia/Qantas Club), Singapore Airlines, Air New Zealand và Emirates đều vận hành các phòng chờ trong nhà ga.
Nhà ga quốc tế lấy ý tưởng dựa trên các tác phẩm của các nghệ sĩ bản địa Úc nổi tiếng gồm Daisy Jugadai Napaltjarri và Gloria Petyarre.
Một chương trình mở rộng trị giá 330 triệu USD cho Nhà ga số 2 được công bố vào năm 2007 và hoàn thành vào năm 2012. Mục tiêu của dự án này bao gồm các phòng chờ và cơ sở bán lẻ mới, một nhà ga vệ tinh mới, tăng băng chuyền nhận hành lý và thiết kế lại các khu vực hải quan và an ninh. Một nhà ga vệ tinh mới có cửa sổ kính trong suốt từ trần đến sàn cho tầm nhìn ra đường băng Bắc-Nam. Khu vực mở rộng bao gồm ba cầu ống lồng đôi là cửa số 16, 18 và 20, mỗi cầu ống lồng chứa máy bay Airbus A380 hoặc hai máy bay nhỏ hơn và một cầu ống lồng đơn. Khu vực nhận hành lý tăng thêm hai băng chuyền.
Mặc dù được mô tả là nhà ga vệ tinh, nhưng nhà ga được kết nối bằng một hành lang trên mặt đất với Nhà ga 2. Các chuyến bay đh diễn ra ở tầng dưới (tương tự như phòng chờ lên máy bay Airbus A380 hiện đang được sử dụng tại cửa số 9 và 11), với chuyến đến được sắp xếp ở tầng một để đồng bộ tầng một sảnh đến.
Nhà ga số 3
Nhà ga số 3 trước kia thuộc sở hữu của Ansett Australia, nhưng hiện thuộc sở hữu của Sân bay Melbourne. Nhà ga số 3 là nhà ga chính của Virgin Australia. Nó có 11 cửa ra máy bay sử dụng ống lồng đơn và 8 cửa ra máy bay không sử dụng ống lồng.
Việc mở rộng nhà ga được phê duyệt vào năm 1989 và hoàn thành vào năm 1991. Nhà ga được Tập đoàn Ansett độc quyền sử dụng cho tất cả các chuyến bay trong nước cho đến khi hãng khai tử vào năm 2001. Nó được dự định sẽ được sử dụng bởi "New Ansett", thuộc quyền sở hữu của Tesna; tuy nhiên, sau khi tập đoàn Tesna rút lại việc mua Ansett vào năm 2002, nhà ga đã được các nhà quản lý của Ansett bán lại cho Sân bay Melbourne. Do đó, Sân bay Melbourne đã tiến hành một cuộc cải tạo lớn và nâng cấp nhà ga. Rex cũng điều hành một phòng chờ trong nhà ga. Trụ thứ hai của nhà ga số 3 đã bị mất vào tay nhà ga số 4, trong số mười cửa ra máy bay họ sẽ giành lại ba cửa. Trong khi được sử dụng bởi Tigerair Australia. Các quầy làm thủ tục cho Virgin Australia sẽ vẫn ở nhà ga số 3.
Nhà ga số 4
Nhà ga số 4 - ban đầu được gọi là Domestic Express hoặc South Terminal - dành riêng cho các hãng hàng không giá rẻ. Ban đầu nó được sử dụng cho Virgin Blue (Virgin Australia) và Impulse Airlines. Virgin Blue cuối cùng đã chuyển đến Nhà ga số 3 sau sự sụp đổ của Ansett. Việc tái trang bị trị giá 5 triệu đô la bắt đầu vào tháng 6 năm 2007 dọc theo mô hình nhà ga ngân sách tại Sân bay Changi Singapore và Sân bay Quốc tế Kuala Lumpur. Phí hạ cánh và xử lý sân bay thấp hơn được tính cho các hãng hàng không do cơ sở vật chất cơ bản, thiếu cầu ống lồng, ít tiện nghi và cửa hàng bán lẻ hơn so với nhà ga thông thường. Tuy nhiên, nhà ga nằm cạnh nhà ga chính, không giống như ở Singapore và Kuala Lumpur. Nhà ga được xây dựng lại bởi Tiger Airways Australia, hãng đã sử dụng nó làm căn cứ chính kể từ khi khai thác chuyến bay nội địa đầu tiên vào ngày 23 tháng 11 năm 2007.
Jetstar xác nhận tham gia vào các cuộc thảo luận với Sân bay Melbourne về việc mở rộng các cơ sở nhà ga để đáp ứng sự phát triển của các dịch vụ giá rẻ nội địa. Việc mở rộng nhà ga số 4 bao gồm cơ sở hạ tầng để phục vụ các chuyến bay của Tiger Airways Australia và Jetstar Airways. Việc phát triển tốn hàng trăm triệu đô la. Vào tháng 3 năm 2012, các quan chức sân bay cho biết nhà ga số 4 sẽ động thổ vào tháng 10 cùng năm và dự kiến hoàn thành vào tháng 7 năm 2014, tuy nhiên sau đó họ đã đẩy ngày hoàn thành đến cuối tháng 8 năm 2015. Nhà ga mở cửa vào ngày 18 tháng 8 năm 2015. Nhà ga số 4 mới rộng 35.000 m2 và được liên kết "dưới một mái nhà" với nhà ga số 3. Nhà ga số 4 hiện được sử dụng bởi Rex Airlines, Jetstar, Airnorth, trước đây là Tigerair Australia và hãng hàng không mới Bonza. Vào tháng 11 năm 2015, Jetstar chuyển sang nhà ga số 4. Ba cửa ra máy bay được dành riêng cho Virgin Australia. Jetstar có số cửa ra máy bay gấp ba lần so với nhà ga số 1.