Scrivi una continuazione per questo paragrafo - La nave è stata posata dalla Walkers Limited, a Maryborough, Queensland, il 1 novembre 1971 e varata il 29 dicembre 1971. È stata commissionata nella RAN come HMAS "Labuan" (numero di stendardo L 128) il 9 marzo 1973. "Labuan" prende il nome dagli sbarchi anfibi della seconda guerra mondiale a
l'isola del Borneo, Labuan. Al suo ingresso in servizio, fu portata a casa a Brisbane.