Two new nemertean species from the deep-sea, Cephalothrix iwatai sp. nov. and Micrura bathyalis sp. nov., are described and illustrated from material collected in the Sea of Japan during the SoJaBio (Sea of Japan Biodiversity Studies) expedition in the summer 2010. Both species represent the deepest benthic nemerteans reported to date. In addition, the diagnosis of the genus Cephalothrix is modified to accommodate recent data on cephalotrichid morphology.