Members of the Cryptochiridae are small, fragile, symbiotic crabs that live in domiciles in modern corals. Despite their worldwide occurrence with over 50 species known today, their fossil record is unknown. We provide the first unambiguous evidence of cryptochirids in the fossil record through their crescentic pits, typical for certain cryptochirids, in Western Atlantic fossil corals, while the Eocene genus Montemagrechirus is excluded from the Cryptochiridae and referred to Montemagrechiridae fam. nov. Nine Pleistocene corals with crescentic pits originate from Florida (USA), and single specimens with pits come from the late Pleistocene of Cuba and the late Pliocene of Florida, all of which are measured for growth analyses. These pits represent trace fossils named Galacticus duerri igen. nov., isp. nov. A study of modern cryptochirid domicile shape (crescentic pit, circular-oval pit, or a true gall) shows that species within crab genera tend to inhabit the same pit shape. Crescentic pits in corals occur not only in the Western Atlantic today, but also in the Indo-West Pacific and in the Eastern Pacific. Thus, examination of Cenozoic fossil coral collections from these regions should yield further examples of cryptochirid pits, which would help to constrain the antiquity of this cryptic crab family.