Six labrid genera, Austrolabrus Steindachner, Dotalabrus Whitley, Eupetrichthys Ramsay & Ogilby, Notolabrus new genus, Pictilabrus Gill, and Pseudolabrus Bleeker, are recognised as forming a monophyletic assemblage, here referred to collectively as pseudolabrines. This group comprises 23 species, including two new species described herein: Dotalabrus alleni n.sp. and Pictilabrus viridis n.sp., both from south-western Australia. The genus Suezichthys (= Suezia) Smith, previously considered closely related to Pseudolabrus, is excluded. Keys, diagnoses and descriptions of the genera and species are given. The pseudolabrines are provisionally placed in the tribe lulidini, and appear to be the plesiomorphic sister group of all other julidines. Within the pseudolabrine group, cladistic analysis supports the separation of Notolabrus n.gen., previously included with Pseudolabrus, and the inclusion of Lunolabrus Whitley as a sub genus of Pseudolabrus.