A new species of symbiotic palaemonid shrimp of the genus Pseudocoutierea Holthuis, 1951, is described based on a specimen collected in the eastern Gulf of Mexico, off the southwest coast of Florida. Pseudocoutierea stephanieae sp. nov., is the seventh known in this genus, and morphologically most similar to P. antillensis Chace, 1972, and P. conchae Criales, 1981, from the western Atlantic, and P. elegans Holthuis, 1952, from the eastern Pacific, all sharing an expanded rostral base or eaves that terminate supra-distally in an acute tooth. This new species can be separated by: the presence of an epigastric knob or tubercle on the anterior mid-dorsal third of the carapace, which is absent in all other congeneric species; the shape of the pterygostomial sinus, which is shallow in this new species, whereas it is deep and well defined in all other congeneric species. An updated dichotomous key to species of Pseudocoutierea is presented.