Vestigial characters are common across the tree of life, but the underlying evolutionary processes shaping phenotypic loss are poorly understood. The mammalian vomeronasal system, which detects social chemical cues important to fitness, is an impressive example of a sensory system lost multiple times. Three times more losses are inferred among bats than in other mammalian orders. We characterized the relationship between amino acid substitutions in a gene tightly linked to vomeronasal function (Trpc2) and the accessory olfactory bulb, a brain region that processes the detection of these vomeronasal chemical cues. By applying a phylogenetic logistic regression, we found a strong negative relationship between the branch lengths representing rates of codon changes in the Trpc2 gene tree and the presence or absence of an accessory olfactory bulb. Longer branch lengths predict loss of the accessory olfactory bulb, suggesting selection has relaxed on the system as a whole. Based on this relationship, we predicted the absence of an accessory olfactory bulb in 19 bat species with unknown morphology. Several species with predicted losses have specialized skull morphology, suggesting a potential tradeoff between adaptation in skull shape and maintenance of the vomeronasal system. This study offers a new approach to relate genetic mechanisms and phenotypes at a macroevolutionary scale.