Callipallenid sea spiders are commonly found in southern Australian waters. The genera Pseudopallene and Stylopallene are frequent epibionts of arborescent bryozoan colonies of Orthoscuticella spp. and Amathia spp. Based on external morphology, colouration patterns, and sequence divergence of nuclear and mitochondrial markers, we differentiate species of Pseudopallene and Stylopallene from southeast Tasmania, New South Wales and Victoria. In this paper we describe five species new to science: P. tasmania, P. gracilis, P. constricta, P. flava and P. harrisi, and propose the 'variabilis'- complex, which is yet to be resolved based on additional material. Also, two species previously known from Southern Australia are reported as new records for Tasmania. The use of molecular data in resolving species identities of Australian Pycnogonida appears crucial, particularly in the understanding of the amazing, yet undiscovered diversity of brightly colourful callipallenid species. The genus Pseudopallene previously known from 20 species distributed in both southern and northern hemispheres now includes 14 Australian endemic species and at least one species complex yet to be resolved.