Paranaitis Southern, 1914 (Phyllodocidae, Polychaeta) is revised based on an examination of all available types and newly collected specimens. Redescriptions are provided of the 11 previously described species considered valid: P. wahlbergi (Malmgren, 1865), P. abyssalis (Hartmann-Schröder, 1975), P. benthicola (Knox, 1960), P. bowersi (Benham, 1927), P. caeca (Moore, 1903), P. gardineri Perkins, 1984, P. inflata (Hutchings & Murray, 1984), P. kosteriensis (Malmgren, 1867), P. polynoides (Moore, 1909), P. speciosa (Webster, 1879) and P. uschakovi Eibye-Jacobsen, 1991. Paranaitis misakiensis sp. nov., P. moritai sp. nov. and P. pumila sp. nov. are described from Japan. Anaitis peremptoria Claparède, 1870; Anaitis zeylanica Willey, 1905; Phyllodoce (Anaitis) papillosa Ehlers, 1887; and Phyllodoce (Anaitis) rubens Grube, 1880 are referred to as Phyllodocidae incertae sedis, and P. capensis (Day, 1960), P. formosa (Verrill, 1885) and P. picta (Verrill, 1885) to as Paranaitis incertae sedis. Phyllodoce truncata (Hartmann-Schröder, 1965) comb. nov. is removed from Paranaitis. Some previously unreported characters are introduced, including a series of proboscis characters, morphology of dorsal cirrophores, and symmetry of rostrum of chaetal shaft. Distinguishing characters for all recognized species of Paranaitis are provided in a table. In order to assess the position and delineation of Paranaitis and the relationships within this taxon, we present a morphology-based parsimony analysis of relationships within the Phyllodocidae. Paranaitis is shown to be paraphyletic at the exclusion of Chaetoparia, although current support does not allow for any formal synonymy. Phyllodoce and the Eteone-group appear as consecutive sister taxa to the Paranaitis-Chaetoparia clade. The monophyly of Notophyllinae is well supported, but low consensus resolution is obtained for the positions of major taxa such as Eulalia, Eumida, and the Mystides-group.