This note describes the first record of the chocolate shrimp-goby Cryptocentrus malindiensis (Smith, 1959) from Réunion Island, based on photographic evidence. A specimen of an estimated total length of 7 cm was photographed at 9:00 AM on 8 November 2012, at a water temperature of 26°C and depth of 8 m, on a prehistoric lava flow of the Piton de la Fournaise volcano. The habitat included shallow-water sea cracks and rocky overhangs, near basaltic muddy sandy bottoms, with a high hard substrate cover of calcareous algae, encrusting sponges and hydroids without coral, reflecting a low-light environment at these latitudes. Significant siltation, probably caused by a nearby river mouth, suggested the presence of a relatively low wave and current energy, which could be the effect of the confined nature of the habitat.