As designed, the ship had a full load displacement of 4,100 tons, a length overall of 138.1 metres (453 ft), a beam of 13.7 metres (45 ft), and a draught of 24.5 metres (80 ft). Propulsion machinery consists of two General Electric LM2500 gas turbines, which provide a combined 41,000 horsepower (31,000 kW) to the single propeller shaft. Top speed is 29 knots (54 km/h; 33 mph), with a range of 4,500 nautical miles (8,300 km; 5,200 mi) at 20 knots (37 km/h; 23 mph. Two 650-horsepower (480 kW) electric auxiliary propulsors are used for close manoeuvring, with a top speed of 4 knots (7.4 km/h; 4.6 mph). Standard ship's company is 184, including 15 officers, but excluding the flight crew for the embarked helicopters.
In 1996, the frigate was deployed to the Persian Gulf.
In 2002, Melbourne participated in the third rotation of RAN ships to the Persian Gulf as part of Operation Slipper, where she enforced United Nations sanctions against Iraq
In 2003, the ship returned to Iraqi waters in support of Operation Catalyst, protecting Iraqi territorial waters following Operation Iraqi Freedom
Following an overhaul of the RAN battle honours system, completed in March 2010, Melbourne was awarded the honours "East Timor 2000" and "Persian Gulf 2002".
On 16 August 2010, Melbourne was deployed to the Middle East for the third time, again as part of Operation Slipper. During the six-month deployment, the frigate participated in anti-piracy operations in the Arabian Sea and responded to 14 distress calls from merchant vessels, including the British chemical tanker MV CPO China on 3 January 2011. Although it took six hours for Melbourne to close with CPO China, the merchant ship's crew secured themselves in the citadel, and the pirates retreated when the frigate and her Seahawk helicopter arrived. Melbourne returned to Sydney on 18 February 2011.
Between 5 and 7 February 2014, while deployed off Tanzania, Melbourne seized and destroyed 575 kilograms (1,268 lb) of heroin from smuggling vessels.
On 18 February, while operating off Oman's Masirah Island, Melbourne and the Pakistani frigate PNS Alamgir intercepted and boarded a dhow found to be carrying 1,951 kilograms (4,301 lb) of cannabis resin.
The ship is operational as of 2016.