Palaemon antennarius H. Milne Edwards, 1837 and Palaemon migratorius (Heller, 1862) are redescribed and differentiated from other circum-Mediterranean members of the genus on the basis of the following characters: (a) lack of mandibular palp, (b) form of first maxilliped endites, (c) form of maxillula palp, (d) number and length of plumose setae at the distal end of telson, and (e) shape of the fifth abdominal pleuron. In addition, two new species of the genus, P. colossus sp. nov. and P. minos sp. nov., are described from Rhodes and Crete, respectively. The new species are distinguished from the hitherto known congeners by the following set of key characters: (a) shape of the fifth abdominal pleuron, (b) number and length of the plumose setae at the distal end of the telson, (c) shape of the endopod of the first pleopod, (d) form of thoracic and abdominal sternal armature and (e) number of the lanceolate setae on the ventral margins of telson.