The ships have a displacement of 2,170 tons at full load.^[1] They are 71.2 metres (234 ft) long, with a beam of 15.2 metres (50 ft), and a draught of 4.3 metres (14 ft).^[1] Main propulsion machinery consists of four GEC Alsthom 6RK 215 diesel generators, which supply two Alsthom electric motors, each driving a propeller shaft.^[1] A Schottel bow thruster is fitted for additional manoeuvrability.^[1] Maximum speed is 13 knots (24 km/h; 15 mph), with a range of 18,000 nautical miles (33,000 km; 21,000 mi) at 9 knots (17 km/h; 10 mph).^[1]

Each ship was originally fitted with a STN Atlas 9600 APRA I-band navigational radar,^[1] now updated to Sperry Vision-Master FT dual X-band and S-Band radar system. The vessels are fitted with a Nautel C-Tech CMAS 36/39 hull-mounted omni-directional active sonar,^[1] updated to CMAS 30D configuration. In addition, the ships were originally fitted with an Atlas Fansweep-20 multibeam echo sounder and an Atlas Hydrographic Deso single-beam echo sounder, and a Klein 2000 towed sidescan sonar array.^[1] These have been updated to a Teledyne Seabat T50 IDH Multi-Beam Echo-Sounder, ship specific Single-Beam Echo-Sounders, and an EdgeTech towed sidescan sonar. The sonars and echo sounders allow the vessels to chart waters up to 6,000 metres (20,000 ft) deep.^[2] There are three sets of davits fitted; although normally used to carry the 10.7-metre (35 ft) Fantome-class survey boats, they can be configured for other small craft.^[1] In addition, they carry a RHIB and two utility boats.^[1] The Leeuwins are fitted with a helicopter deck for an AS 350B Squirrel helicopter, although lack long-term hosting facilities.^[1] They are armed with two single 12.7 mm machine guns.^[2]

The ship's company consists of 10 officers and 46 sailors.^[1] In addition, up to 5 trainees can be accommodated.^[1] The Leeuwins were the first RAN ships to use a multi-crewing concept,^{[citation needed]} with three complements used to operate the two vessels.^[2] Both vessels currently operate with a permanent single complement each.

The two ships were ordered from NQEA Australia on 2 April 1996, and built at the company's shipyard in Cairns, Queensland.^[1] Construction of Leeuwin commenced in August 1996, and she was launched in July 1997, while Melville was laid down in May 1997 and launched in June 1998.^[2] The vessels underwent a joint commissioning ceremony on 27 May 2000.^[1] The ships initially bore the pennant numbers "HS 01" and "HS 02" respectively, but these were changed in 2004 to "A 245" and "A 246".^[2]

Both Leeuwin and Melville are based at HMAS Cairns.^[1] They operate in support of the Australian Hydrographic Office.^[2]

In late 2001, both ships began operations to supplement patrol forces and counter illegal immigration as part of Operation Relex, in addition to normal surveying duties.^[2][3] The survey ships were selected as they had greater range and seakeeping capabilities that the Fremantle-class patrol boats.^[3] In January 2002, Leeuwin and Melville were repainted from white to grey.^[2][3]

• Bateman, Sam; Bergin, Anthony; Tsamenyi, Martin; Woolner, Derek (2006). "Integrated maritime enforcement and compliance in Australia". In Rothwell, Donald R.; VanderZwaag, David L. (eds.). Towards principled oceans governance: Australian and Canadian approaches and challenges. Oxon: Routledge. ISBN 978-0-415-38378-3.
• Saunders, Stephen, ed. (2008). Jane's Fighting Ships 2008–2009. Jane's Fighting Ships (111th ed.). Surrey: Jane's Information Group. ISBN 9780710628459. OCLC 225431774.
• Wertheim, Eric, ed. (2007). The Naval Institute Guide to Combat Fleets of the World: Their Ships, Aircraft, and Systems (15th ed.). Annapolis, MD: Naval Institute Press. ISBN 9781591149552. OCLC 140283156.

• "Surveying Ship (AGS)". Royal Australian Navy.