Crematogaster ( Crematogaster) jehovae var. cypria Santschi, 1930 is raised to species rank. Two new, related species are described from the north-eastern part of the Mediterranean Basin: Crematogaster ( Crematogaster) erectepilosa sp. n. (Dodecanese, Greece) and Crematogaster ( Crematogaster) gullukdagensis sp. n. (Antalya Prov., Turkey). These three species are well distinguished from other species of the subgenus Crematogaster of the north-eastern part of the Mediterranean Basin in their first gastral tergite bearing numerous erect setae. Colour photographs of all taxa are provided, a key to the species of Crematogaster cypria group and species groups of the Crematogaster s. str. from the north-eastern Mediterranean region are given and a list of Crematogaster s. str. described from this region is provided (see Appendix).