Cytherois gajinensis sp. nov. is described and Violacytherois sargassicola (Hiruta, 1976) is redescribed. The species have been collected from littoral and interstitial waters in South Korea. They belong to Cytheroisinae , one of the three Paradoxostomatidae subfamilies. Both species are the first taxonomic records of the subfamily in Korea. Taxonomic keys to the living Paradoxostomatidae genera are provided in an attempt to clarify the position of some of the currently included genera as well as a key to East Asian Cytheroisinae species in order to facilitate further biodiversity research in the region.