Mushroom corals of the Indo-West Pacific Fungiidae (Scleractinia) provide habitats for a rich associated fauna, including three species of gall crabs (Cryptochiridae). During the course of the present study gall crabs were sampled from many different fungiid hosts. Based on this ‘reversed’ approach - by studying coral symbionts from a host perspective - a previously unnoticed host specificity pattern was detected. The sampling of gall crab fauna per host coral combined with molecular analyses of H3 nDNA, 16S and COI mtDNA revealed a cryptic gall crab species closely related to Fungicola fagei. This new species, described hereafter as Fungicola syzygia sp. nov., is predominantly associated with the mushroom coral genera Cycloseris and Pleuractis, whereas its sibling species F. fagei is only known to be associated with the host genera Podabacia and Sandalolitha. Based on morphology F. syzygia sp. nov. is difficult to distinguish from F. fagei, but there are subtle differences in carapace shape, the lateral carapace margins, the border between the orbital angles and the merus of the third maxilliped, as well as in the carapace length/width ratio. The type material of F. utinomi and F. fagei is figured for comparison.