Thousands of species of ambrosia beetles excavate tunnels in wood to farm fungi. They maintain associations with particular lineages of fungi, but the phylogenetic extent and mechanisms of fidelity are unknown. We test the hypothesis that selectivity of their mycangium enforces fidelity at coarse phylogenetic scales, while permitting promiscuity among closely related fungal mutualists. We confirm a single evolutionary origin of the Xylosandrus complex – a group of several xyleborine genera that farm fungi in the genus Ambrosiella. Multi-level co-phylogenetic analysis revealed frequent symbiont switching within major Ambrosiella clades, but not between clades. The loss of the mycangium in Diuncus, a genus of evolutionary cheaters, was commensurate with loss of fidelity to fungal clades, supporting the hypothesis that the mycangium reinforces fidelity. Finally, in-vivo experiments tracked symbiotic compatibility throughout the symbiotic life cycle of Xylosandrus compactus and demonstrated that closely related Ambrosiella symbionts are interchangeable, but the probability of fungal uptake in the mycangium was significantly lower in more phylogenetically distant species of symbionts. Symbiont loads in experimental subjects were similar to wild-caught beetles. We conclude that partner choice in ambrosia beetles is achieved biochemically in the mycangium, and co-phylogenetic inferences can be used to predict the likelihood of specific symbiont switches.