Phytoplankton-bacteria interactions represent the evolution of complex cross-kingdom networks requiring niche specialization of diverse microbes. Unraveling this co-evolutionary process has proven challenging because microbial partnerships are complex, and their assembly can be dynamic as well as scale- and taxon-dependent. Here we monitored long-term experimental evolution of phytoplankton-bacteria interactions by reintroducing the intact microbiome into an axenized dinoflagellate Alexandrium tamarense to better understand microbiome assembly dynamics and how microbiome composition could shift and stabilize over 15 months. We examined host functioning by growth rate, photosynthetic capability, cell size, and other physiological signatures and compared it to associated microbial communities determined by 16S rRNA gene sequences. Our results showed that microbiome reconstitution did not restore the intact microbiome, instead a distinct microbial community shift to Roseobacter clade was observed in the re-established cultures. In-depth comparisons of microbial interactions revealed no apparent coupling between host physiology and specific bacterial taxa, indicating that highly represented, abundant taxa might not be essential for host functioning. The emergence of highly divergent Roseobacter clade sequences suggests fine-scale microbial dynamics driven by microdiversity could be potentially linked to host functioning. Collectively, our results indicate that functionally comparable microbiomes can be assembled from markedly different, highly diverse bacterial taxa in changing environments.