A new goby species, Speleogobius llorisi sp. nov. (Teleostei: Gobiidae) is described from the circalittoral sea bed at 46-69 m depth off the Balearic Islands, western Mediterranean. Six specimens, four females and two males, of the new species were collected from beam trawl samples carried out on the red algae beds off the south west coast of Mallorca Island. Among others, the main traits that differentiate the new species from the only congeneric species, S. trigloides, are the presence of preopercular head canal with pores γ, δ, ε vs. preopercular head canal absent; a longer snout, equal or longer than eye vs. shorter than eye; lower lip ending anteriorly slightly in front of upper lip vs. upper lip slightly protruding lower lip; scales in lateral series 28 or 29 vs. 26; scales in transverse series 6 vs.7-8. It also differs from S. trigloides in some non-overlapping morphometrics and in coloration. All individuals of the new species were collected from Peyssonnelia beds, beds of red algae dominated by species of the family Peyssonneliaceae. The generic diagnosis of Speleogobius is revised.