The shallow-water tanaidacean fauna of the Bass Strait has been the subject of recent intensive studies. The present paper extends this work into the deeper waters of the region, describing two new species and one new genus. The new species of the genus Paradoxapseudes has a combination of three maxillule palp setae, no plumose setae on the basis of pereopod 1 nor proximal serration on the antennal peduncle. The second species represents a new genus of the family Anarthruridae, having six marginal setae on the third maxilliped palp article and spines on the merus and carpus of the anterior pereopods. The high diversity of Tanaidacea in Australian waters is discussed. In particular, we conclude that Australian coasts suffer a diversity of immigration routes, have sufficient marine longevity, and afford such a diversity of available niches to have allowed multiple colonization and subsequent allopatric speciation of Tanaidacea.