Periclimenes rathbunae Schmitt, 1924 is a western Atlantic symbiotic shrimp species mainly associating with anemones. Adult shrimps of P. rathbunae are characterised by an orange-white spotted colour pattern. During fieldwork along the coast of Curaçao (2013), morphologically similar, though generally smaller sized shrimps were collected from the stony coral Dendrogyra cylindrus Ehrenberg, 1834. These specimens were overall more translucent. This study elucidates the taxonomic status of the coral-associated specimens in relation to anemone-associated specimens of P. rathbunae and related anemone-associated species using one nuclear (histone H3, H3), a mitochondrial protein-coding (cytochrome oxidase subunit I, COI) and a mitochondrial ribosomal RNA (16S) gene. Molecular phylogenetic reconstructions clustered the coral-associated specimens with anemone-associated P. rathbunae within a distinct clade, revealing that the aberrant coral-associated shrimp specimens belong to P. rathbunae. It can be concluded that 1) the stony coral D. cylindrus is a host of P. rathbunae, constituting the first record of an association between a scleractinian coral and a palaemonid shrimp species in the Atlantic Ocean; 2) the colour pattern of P. rathbunae is a phenotypically plastic characteristic that varies with size and is depending on the host species; and 3) mean body size of P. rathbunae is smaller on D. cylindrus than on the anemone Stichodactyla helianthus. This raises interesting questions about patterns of host use for this species and warrants further in-depth field ecological study for this species.