The phyllodocid polychaete Paranaitis wahlbergi occurs in Arctic and northern European boreal waters. Boreal populations are distinct from Arctic ones in having smaller maximal size and larger eggs; in all other respects we find them morphologically inseparable. Phylogenetic analyses and haplotype networks based on the mitochondrial genes 16S rDNA and COI, and the nuclear genes histone H3, ITS1, ITS2, 18S rDNA and 28S rDNA D1-D2 region confirm our suspicion that Arctic and boreal populations belong to different species. We describe the boreal form as a new species, Paranaitis katoi. It is presently known from the Swedish and Norwegian west coasts and from Scotland. Calibrated rates for COI indicate that P. katoi sp. nov. and P. wahlbergi may have been separate for as long as 29-56 million years.