Brown algae of the genus Cystoseira sensu lato form the most diverse and productive marine ecosystems throughout the Mediterranean Sea and have equal roles also in the Black Sea where they have been decreasing in the recent years. The taxonomy of Cystoseira s.l. taxa from the Black Sea is still not well understood, and questions arise when related taxa have to be delimited. In addition to morphological descriptions, this study provides for the first time molecular data of the Black Sea Cystoseira s.l. distinct morphologies as an additional tool to clarify their identities and phylogenetic affinities. The analysis of two mitochondrial markers (cytochrome oxidase subunit 1—COI, and 23S-tRNAVal intergenic spacer—mt-spacer) showed that Cystoseira s.l. specimens from the Black Sea belong to two recently resurrected genera, namely Gongolaria and Ericaria. Molecular data confirm the morphological identification of G. barbata, which is characterized by high morphological plasticity in the Black Sea. The morphological data presented in this study support the transition of G. barbata to the genus Gongolaria, which was previously proposed based solely on genetic data. For the Black Sea endemic taxon C. bosphorica, sequence divergence suggests conspecificity with Mediterranean Sea species E. crinita and E. barbatula. However, considering original morphological characteristics of the taxon, its geographical isolation, and endemism, the new combination Ericaria crinita f. bosphorica comb. nov. is proposed.