The success of tropical scleractinian corals depends on their ability to establish symbioses with microbial partners. Host traits and evolution are known to shape the coral microbiome, but to what extent they affect its composition remains unclear. Here, by using twelve coral species representing the complex and robust clades, we show that functional traits and host evolutionary history explain 14% of the tissue and 13% of the skeletal microbiome composition, providing evidence that these predictors contribute to shaping the holobiont in terms of the presence and abundance of key bacterial species. Additionally, our study shows that the coral tissue and skeleton are dominated by rare bacteria and the skeleton can function as a microbial reservoir. Together, we provide novel insights into the processes driving coral-bacterial symbioses along with an improved understanding of the scleractinian tissue and skeleton microbiome.