Beneath the coral tissue, within the calcium carbonate skeleton, a green layer containing the alga Ostreobium is often visible. Ostreobium is the primary algal symbiont within the coral skeleton and the second major photosynthetic organism in the coral holobiont. In contrast, Symbiodiniaceae represents the major group of marine microalgae that form obligate endosymbiotic relationships with the coral host. While interactions between Symbiodiniaceae and bacteria within the coral holobiont have been extensively studied, many questions remain about the functional dynamics between Ostreobium and its bacterial associates. Ostreobium was recently found to show phylosymbiosis, an association between host phylogeny and bacterial community composition. The drivers of this phylosymbiotic signal are still unknown but may arise from the core microbiome's functions and potential long-term evolutionary associations. In this study, we investigated the functional and evolutionary relationships between Ostreobium (five Ostreobium clades) and its closely associated bacterial microbiome using shotgun sequencing data to assemble metagenome-assembled genomes (MAGs). We identified a rich repertoire of nitrogen-cycling genes and three potential pathways through which energy-efficient ammonia could be produced for algal consumption. Additionally, we discovered the widespread presence of vitamin B12 synthesis potential and C1-metabolizing genes among taxonomically diverse bacteria. Furthermore, we identified MAGs belonging to Phycisphaeraceae, SM1A02, GWC2-71-9, and Amoebophilaceae that were enriched with Ankyrin repeats, proteins thought to be involved in maintaining host associations. To explore the evolutionary relationships, we conducted a cophylogenetic analysis to assess the phylogenetic congruence between Ostreobium hosts and their bacterial associates. Our analysis indicated a notable phylogenetic congruence between Phycisphaerales bacteria and Ostreobium hosts, shedding light on possible long-term and intimate associations contributing to the phylosymbiotic signal. Overall, our study advances the understanding of functional and evolutionary dynamics within algal-bacterial symbiotic systems, providing valuable new insights into the role of algal microbiomes in the broader context of the coral holobiont.