Nine taxa of Miocene baleen whales were described from the Black Sea region under the name Cetotherium before 1951, and a further four closely related species representing three genera have been added in recent years. This rich diversity requires taxonomic revision and ordering. Here, a new genus, Mithridatocetus, is described from the Tortonian of Crimea and Caucasus, with two species, M. eichwaldi and M. adygeicus (originally Kurdalagonus adygeicus); ‘Cetotherium’ mayeri (a nomen dubium) is also a member of this genus. In comparison with other Cetotheriinae, Mithridatocetus is distinguished by the autapomorphic shape of the tympanic bulla with the swollen main ridge, the lowered anterior portion of the involucrum and the oblique anterolateral margin; such synapomorphies, as a transversely narrow squamosal with the ventromedially oriented postglenoid process (shared with Eucetotherium), a squamosal cleft (shared with Kurdalagonus) and an oval surface of the compound posterior process of the tympanoperiotic on the posterolateral skull wall (shared with Brandtocetus); and a unique combination of a high neurocranium and a long and robust paroccipital process. The genus Kurdalagonus is redefined here as containing only one described species, K. mchedlidzei. Therefore, the group Cetotheriinae is now restricted to the latest Serravallian and Tortonian of the Eastern Paratethys and includes at least five genera: Cetotherium, Brandtocetus, Kurdalagonus, Mithridatocetus and Zygiocetus. In addition, ?Cetotherium priscum and C. incertum are considered to be nomina dubia; ‘Cetotherium’ klinderi and ‘Cetotherium’ pusillum require more complete specimens for reassessment; ‘Cetotherium’ maicopicum and Eucetotherium helmersenii require further research to identify their taxonomical affinities.