Ostreobium sp. is the major algal symbiont of the coral skeleton. It lives in extreme conditions of low-light and variable O2 concentrations and fluctuating pH. In contrast to the open ocean, the enclosed nature of the coral skeleton reduces the dispersal and exposure of these residing bacteria to the outside environment. Algae microbiomes can support algal nutritional requirements, and in the enclosed extreme environment these associations between algae and bacteria may be stronger. Here, we describe the bacterial communities associated with cultures of 5 Ostreobium strains. We employed two DNA extraction approaches; one targeting to amplify all the associated bacteria and the other to enhance the capture of closely associated and potentially intracellular communities. In the latter, algal filaments were serially washed, cut open in an extraction buffer letting the cytoplasm to flow out and finally collected for DNA extraction and sequencing. Core microbiome analysis and indicator taxa representing closely associated and potentially intracellular communities helped to identify the bacteria that may support crucial functions of Ostreobium. We finally evaluated the bacterial community compositions to test for phylosymbiosis, the reflection of the host phylogeny in the microbiome community relationships. 16S rRNA gene metabarcoding data revealed distinct and highly diverse bacterial communities representing 19 Phyla spanning 65 families and 54 genera. Proteobacteria and Bacteroidetes were the most dominant phyla accounting for a total relative abundance >87%. The most dominant bacterial family was represented by a methylotrophic bacterium, Methyloligellaceae. The most abundant core families were Methyloligellaceae, Rhodobacteraceae and Rhizobiaceae. Indicator species analysis revealed that members of PAUC34f and Cyclobacteriaceae may represent the closely associated and intracellular bacteria. Significant patterns of phylosymbiosis was detected revealing host influence on shaping the microbiome. Overall, we provide the first study on the Ostreobium microbiome, shed light on phylosymbiotic signatures of an algal-bacterial system and improve our understanding on the coral holobiont.