Paralamyctes Pocock, 1901 has a classic Gondwanan distribution, with species previously known from New Zealand, southern Africa, Madagascar and Chile. The genus as hitherto conceived is paraphyletic, with Triporobius Silvestri, 1917 (India) and Haasiella Pocock, 1901 (New Zealand, Tasmania) nesting within the group. Species from Argentina and New Caledonia originally assigned to Paralamyctes belong to Analamyctes Chamberlin, 1955. Revision of Paralamyctes based upon monophyletic subgroups recognizes four subgenera: P. (Paralamyctes), P. (Haasiella), P. (Nothofagobius) n.subgen. and P. (Thingathinga) n.subgen. The eastern Australian occurrence of Paralamyctes is demonstrated by six new species. Paralamyctes (Thingathinga) grayi n.sp. is distributed from the Blue Mountains to the Budawang Range, New South Wales; P. (Thingathinga) from the Barrington Tops may be specifically distinct. Paralamyctes (T.) grayi and the allied P. (T.) hornerae n.sp. from northern New South Wales have affinities to the New Zealand P. (T.) validus. Paralamyctes (Nothofagobius) cassisi n.sp. occurs in northern New South Wales, while the closely related P. (N.) mesibovi n.sp. inhabits northern Tasmania. Australian P. (Nothofagobius) is sister to the Patagonian P. (N.) chilensis (Gervais), which is illustrated based upon new collections. Paralamyctes (Paralamyctes) monteithi n.sp. is widespread in Queensland; P. (P.) neverneverensis n.sp. is endemic to the Dorrigo region, northern New South Wales. In addition to these two Australian species, the nominate subgenus occurs in New Zealand, southern Africa, Madagascar and India, the latter record based on the junior subjective synonym Triporobius. All new species are included in a key to Australian Lithobiomorpha.