A new Lessepsian migrant, Diplogrammus randalli Fricke 1983, is recorded for the first time from the Mediterranean Sea. This species is easily distinguished from other Mediterranean callionymid fishes by its ventrolateral fold skin below the lateral line and its preopercular spine shape.