Постройка авианосца была начата для ВМС Военно-морские силы Великобритании, под названием Маджестик, в годы Второй мировой войны. Корабль был заложен в 1943 году, однако с окончанием войны его строительство, как и других представителей типа, было остановлено.

В 1949 году корабль был продан ВМС Военно-морские силы Австралии и закончен уже для них, по модернизированному проекту с угловой полетной палубой (5.5гpад).

"Мельбурн" оставался на вооружении в течение более чем четверти века. Получил неофициальное прозвище "Держись подальше» и было за что.

10.02.1964 столкнулся с эсминцем Voyager. Повреждена носовая часть корпуса авианосца, из 314 человек экипажа затонувшего эсминца погибли 82 человека. Поставлен на ремонт в Cackatoo Island Dockyard (приварена 40-тонная носовая секция).

3.06.1969 во время учений в Южно-Китайском море столкнулся в американским эсминцем DD Destroyer (эскадренный миноносец)-754 Frank E. Evans. Эсминец разломился на две части, затонула кормовая часть корпуса, погибли 74 человека экипажа. Поставлен на ремонт Cackatoo Island Dockyard в ноябре 1969 г. (установлена новая носовая секция).

В 1966—1967 годах корабль прошёл модернизацию для операций с новыми, более тяжёлыми самолётами. В 1982 году был выведен в резерв, а в 1985 году был окончательно снят с вооружения и продан на слом в Китай в 1985 г