We describe Proceraea albocephala, new species, from Madeira, and Erseia oligochaeta, new genus and new species, from Istria, Croatia, and we provide redescriptions of Proceraea madeirensis (Nygren, 2004) from topotype material, and Myrianida longoprimicirrata (López, San Martín & Jimenéz, 1997) from material collected at Istria, Croatia, and Banyuls-sur-Mer, France. Proceraea albocephala, new species is morphologically separated from similar species by a prostomial white spot, and E. oligochaeta, new genus, new species is unique in having only a few (1–2) simple unidentate chaetae in all chaetigers, and a trepan with a single large and 25–28 smaller teeth. We assess the phylogenetic positions of the four species using nuclear 18SrDNA, together with mitochondrial COI and 16SrDNA. Our molecular data show that among the sequenced autolytines 1) P. albocephala, new species is most closely related to P. nigropunctata Nygren & Gidholm, 2001, P. okadai (Imajima, 1966), and P. cornuta (Agassiz, 1862), 2) E. oligochaeta, new genus, new species belongs within a clade together with Procerastea nematodes Langerhans, 1884, Virchowia clavata Langerhans, 1879, and Imajimaea draculai (San Martín & López, 2002), 3) M. longoprimicirrata is sister species to M. pentadentata (Imajima, 1966), and 4) P. madeirensis has a basal position within Procerini. The molecular data suggests that Proceraea Ehlers, 1864 as currently delineated is paraphyletic.