Two new free-living marine nematode species of Cyatholaimidae, Marylynnia gracila sp. nov. and Paracanthonchus heterocaudatus sp. nov. from the Yellow Sea, China are described. Marylynnia gracila sp. nov. is characterized by slender body, long inner labial setae, absence of lateral differentiation, gubernaculum strongly cuticularized and distal half expanded with two curving teeth, six cup-shaped precloacal supplements. Paracanthonchus heterocaudatus sp. nov. is characterized by tail sexually dimorphic: male tail short (4.4 a.b.d.), conical, with short distal cylindrical portion, with lateral differentiation of the cuticle, two subventral rows of five setae at the anterior part of tail, and two ventral swelling each with a pair of short stout setae at the posterior part of tail; female tail long (7.1 a.b.d.) with longer distal cylindrical part, without caudal setae and lateral differentiation of the cuticle; spicules slender, slightly bent, cephalate proximally and tapering distally, gubernaculum arcuate, middle portion expanded and gradually narrowing with two curving teeth at distal end, six small tubular precloacal supplements in a 2+4 arrangement. The same time, the key to species of Marylynnia has been provided.