Marine invertebrates harbour a complex suite of bacterial and archaeal symbionts, a subset of which are probably linked to host health and homeostasis. Within a complex microbiome it can be difficult to tease apart beneficial or parasitic symbionts from nonessential commensal or transient microorganisms; however, one approach is to detect strong cophylogenetic patterns between microbial lineages and their respective hosts. We employed the Procrustean approach to cophylogeny (PACo) on 16S rRNA gene derived microbial community profiles paired with COI, 18S rRNA and ITS1 host phylogenies. Second, we undertook a network analysis to identify groups of microbes that were co-occurring within our host species. Across 12 coral, 10 octocoral and five sponge species, each host group and their core microbiota (50% prevalence within host species replicates) had a significant fit to the cophylogenetic model. Independent assessment of each microbial genus and family found that bacteria and archaea affiliated to Endozoicomonadaceae, Spirochaetaceae and Nitrosopumilaceae have the strongest cophylogenetic signals. Further, local Moran's I measure of spatial autocorrelation identified 14 ASVs, including Endozoicomonadaceae and Spirochaetaceae, whose distributions were significantly clustered by host phylogeny. Four co-occurring subnetworks were identified, each of which was dominant in a different host group. Endozoicomonadaceae and Spirochaetaceae ASVs were abundant among the subnetworks, particularly one subnetwork that was exclusively comprised of these two bacterial families and dominated the octocoral microbiota. Our results disentangle key microbial interactions that occur within complex microbiomes and reveal long-standing, essential microbial symbioses in coral reef invertebrates.