Coral-associated microorganisms are thought to play a fundamental role in the health and ecology of corals, but understanding of specific coral-microbial interactions are lacking. In order to create a framework to examine coral-microbial specificity, we integrated and phylogenetically compared 21,100 SSU rRNA gene Sanger-produced sequences from bacteria and archaea associated with corals from previous studies, and accompanying host, location and publication metadata, to produce the Coral Microbiome Database. From this database, we identified 39 described and candidate phyla of Bacteria and two Archaea phyla associated with corals, demonstrating that corals are one of the most phylogenetically diverse animal microbiomes. Secondly, this new phylogenetic resource shows that certain microorganisms are indeed specific to corals, including evolutionary distinct hosts. Specifically, we identified 2-37 putative monophyletic, coral-specific sequence clusters within bacterial genera associated with the greatest number of coral species (Vibrio, Endozoicomonas and Ruegeria) as well as functionally relevant microbial taxa ("Candidatus Amoebophilus", "Candidatus Nitrosopumilus" and under recognized cyanobacteria). This phylogenetic resource provides a framework for more targeted studies of corals and their specific microbial associates, which is timely given the escalated need to understand the role of the coral microbiome and its adaptability to changing ocean and reef conditions.