Three new species of pinguipedid fishes from northern Australia are described based on specimens collected by deep water demersal trawling. Parapercis algrahami sp. nov. is recorded from off Dunk Island, Qld, south to Newcastle, NSW, in 67–333 m. It is distinct in having five narrow transverse dark bars across the upper body and a dark spot dorsally on the caudal-fin base, 6 canine teeth in outer row at front of lower jaw, palatines with 1–2 rows of teeth, and predorsal scales extending far forward on the nape to the posterior portion of the interorbital region. Parapercis imamurai sp. nov. is recorded from off Saumarez Reef, Qld, south to off Coffs Harbour, NSW, in 256–405 m. It is unique in having colouration that includes a broad dusky bar from lower margin of eye across the suborbital region and three broad dusky bands crossing the body between the middle of the soft dorsal-fin and the caudal-fin base, 10 canine teeth in outer row at front of lower jaw, and the fifth dorsal-fin spine longest. Parapercis pogonoskii sp. nov. is unique in having a combination of three reddish-brown vertical bars on the upper body between the anterior and posterior portions of the soft dorsal fin, the soft dorsal fin with two large dusky blotches and caudal-fin base with a dusky blotch in the upper corner, 8–10 canine teeth in outer row at front of lower jaw, fifth dorsal-fin spine longest, angle of subopercle with a single broad spine, and angle of preopercle with 4–5 large widely-separated spines. Comparison of the mitochondrial cytochrome c oxidase subunit 1 (CO 1) genetic marker utilised in DNA barcoding produced significant genetic divergences of at least 8.1% and 14.1% between P. algrahami sp. nov. and P. pogonoskii sp. nov. respectively and their closest sampled congeners. The geographic range of Parapercis rubromaculata Ho, Chang & Shao, 2012 is extended from Taiwan to the southern hemisphere waters off Western Australia, based on specimens collected from Shark Bay, north to Ashmore Terrace, in depths of 56–107 m. A revised diagnosis for the species is presented, meristic, morphometric and DNA barcoding data for the two populations are compared, and a detailed description of the colouration of fresh and preserved specimens from Australia is provided. Previous records of Parapercis macrophthalma (Pietschmann, 1911) from Western Australia are established as misidentifications of Parapercis muronis (Tanaka, 1918) and the latter is thereby confirmed from the southern hemisphere and Australian waters for the first time. Comparative meristic, morphometric and DNA barcoding data is provided for populations of P. muronis from Japan, Philippines and Western Australia.