Scleractinian corals' microbial symbionts influence host health, yet how coral microbiomes assembled over evolution is not well understood. We survey bacterial and archaeal communities in phylogenetically diverse Australian corals representing more than 425 million years of diversification. We show that coral microbiomes are anatomically compartmentalized in both modern microbial ecology and evolutionary assembly. Coral mucus, tissue, and skeleton microbiomes differ in microbial community composition, richness, and response to host vs. environmental drivers. We also find evidence of coral-microbe phylosymbiosis, in which coral microbiome composition and richness reflect coral phylogeny. Surprisingly, the coral skeleton represents the most biodiverse coral microbiome, and also shows the strongest evidence of phylosymbiosis. Interactions between bacterial and coral phylogeny significantly influence the abundance of four groups of bacteria-including Endozoicomonas-like bacteria, which divide into host-generalist and host-specific subclades. Together these results trace microbial symbiosis across anatomy during the evolution of a basal animal lineage.