Two new species of Paraopisthosyllis are described herein, P. correiae sp. nov. (State of Pernambuco, NE Brazil) and P. kuluguhin sp. nov. (Philippines). Paraopisthosyllis correiae sp. nov. represents the first record for the genus in Brazilian waters and it is also the second species known to occur outside the Pacific Ocean. This species is characterized by having a marked color pattern, with a transverse red stripe between dorsal cirri on each segment and an inverted V anteriorly and a V posteriorly on some segments, small papillae on body, large, distinct papillae on dorsal cirri, compound chaetae with elongated, bidentate blades, shafts with moderate subdistal serration on margin, pharyngeal tooth located on anterior third of pharynx, near the pharyngeal opening, and reproduction by schizogamy. Paraopisthosyllis kuluguhin sp. nov. represents the first report of the genus for the Philippines, together with P. pardus, originally known from Australia and also found in the Philippines in the present study. This new species is characterized by its color pattern, with dark patches irregularly distributed on anterior segments, forming one anterior pigmented short band and two lateral areas on each chaetiger after the proventricle, club-shaped dorsal cirri, and short, bidentate compound chaetae. Our findings allow us to synonymize the genus Basidiosyllis to Paraopisthosyllis and represent the first report of sexual stolons (scissiparity) in this genus, which supports its allocation into the subfamily Syllinae.