Gobius cruentatus Gmelin, 1789 is an eastern Atlantic goby, occurring from the southwest Ireland to Senegal and in the Mediterranean (Miller, 1986). It is a common species on the inshore rocky habitats, sand with stones and boulders and on the sea-grass meadows in this area (Miller, 1986). The red-mouthed goby is a frequent and abundant benthic species in its characteristic habitat. The most eastern records of this species were from the Anatolian coast of the Aegean Sea and the Sea of Marmara (Miller, 1986; Bilecenoglu et al., 2002). The present finding at the southeast coast of the Black Sea is the first record for the Black Sea and extends the known distribution area of the species (Fig. 1). The urgency of studies on biological diversity of the Black Sea gobies is determined by the problems of taxonomy and zoogeography of the native gobies and by the problem of the extension of the Mediterranean fauna to the Black Sea or "Mediterranization" (Vasil'eva and Bogorodskii, 2004).