Bacteria, fungi and green algae are common inhabitants of coral skeletons. Their diversity is poorly characterized because they are difficult to identify with microscopy or environmental sequencing, as common metabarcoding markers have low phylogenetic resolution and miss a large portion of the biodiversity. We used a cost-effective protocol and a combination of markers (tufA, 16S rDNA, 18S rDNA and 23S rDNA) to characterize the microbiome of 132 coral skeleton samples. We identified a wide range of prokaryotic and eukaryotic organisms, many never reported in corals before. We additionally investigated the phylogenetic diversity of the green algae - the most abundant eukaryotic member of this community, for which previous literature recognizes only a handful of endolithic species. We found more than 120 taxonomic units (near species level), including six family-level lineages mostly new to science. The results suggest that the existence of lineages with an endolithic lifestyle predates the existence of modern scleractinian corals by ca. 250my, and that this particular niche was independently invaded by over 20 lineages in green algae evolution. These results highlight the potential of the multi-marker approach to assist in species discovery and, when combined with a phylogenetic framework, clarify the evolutionary origins of host-microbiota associations.