The Paluma-class vessels have a full load displacement of 320 tonnes.[1] They are long overall and long between perpendiculars, have a beam of, and a draught of .[1] Propulsion machinery consists of two General Motors Detroit Diesel 12V-92T engines, which supply to the two propeller shafts.[1] Each vessel has a top speed of, a maximum sustainable speed of (which gives a maximum range of), and an endurance of 14 days.[1]
The sensor suite of a Paluma-class launch consists of a JRC JMA-3710-6 navigational radar, an ELAC LAZ 72 side-scan mapping sonar, and a Skipper 113 hull-mounted scanning sonar.[1] The vessels are unarmed.[1] The standard ship's company consists of three officers and eleven sailors, although another four personnel can be accommodated.[1] The catamarans were originally painted white, but were repainted naval grey in 2002.[1]
Benalla was laid down by Eglo Engineering, on 25 November 1988, was launched on 31 January 1990, and commissioned into the RAN on 20 March 1990.[1] The ship was named for the city of Benalla, Victoria.
In October 2013, Benalla participated in the International Fleet Review 2013 in Sydney.[2]
HMAS Benalla, along with were decommissioned at on 16 June 2023, with the acceleration of the Defence Strategic Review released in May 2023.[3]