Phycosphere is microscopical niche for cross-kingdom algae-bacteria interactions (ABI), and hosts unique microbial holobionts of phycosphere microbiota (PM) which play crucial roles in aquatic ecosystems. Exopolysaccharides (EPS) serve as vital chemical interface for bacterial colonization and attachment, nutrient exchanges and signalling within phycosphere during these dynamic associations. The PM has proven a unique prokaryote group and unlimited source for discovering promising natural bioflocculants which bacterial EPS serve as core bioflocculating components. Currently, still little is known about natural potentials for bioflocculant EPS production harboring in PM of toxic harmful algal blooms (HAB) algal species. In this study, to expand this scale, we elucidated the genetic diversity of EPS biosynthesis and potential algae-bacteria interactions of diverse PM of 12 HAB marine dinoflagellates and freshwater cyanobacteria, including 10 marine dinoflagellates cultures including six Alexandrium spp. (three toxic and two non-toxic), one toxic Ostreopsis sp., one non-toxic Prorocentrum mexicanum and two freshwater cyanobacteria, Microcytis aerusinosa (toxic M.TN04 and non-toxic M.TN05) by metagenomics analysis. Comparative genomics was used to characterized genetic variety between 17 new PM bacterial strains as novel species or genera, including Maricaterella alexandrii LZ-14T, Haliea alexandrii LZ-16-2T, Marinobacter shengliensis subsp. alexandrii LZ-6T, Marinobacter alexandrii LZ-8T, Limnobacter alexandrii LZ-4T, Mesorhizobium alexandrii Z1-4T, Nitratireductor alexandrii Z3-1T, Hoeflea prorocentri PM5-8T, Marivita cryptomonadis LZ-15-2, Maritimibacter alexandrii LZ-17T, Mameliella alba LZ-28, Maricaulis alexandrii LZ-16-1T, Ponticoccus alexandrii AT2-AT, Saccharospirillum alexandrii LZ-5T, Sulfitobacter alexandrii AM1-D1T, Sphingopyxis microcytisis Z10-6T and Nioella ostreopsis Z7-4T based on optimized high-throughout culture strategy at our ABI group. The bioflocculation performances of EPS of the PM isolates were evaluated by flocculating rate measurement. The integrated characterization clearly indicates that the PM of 12 HAB algal species could serve as excellent natural candidate for discovering novel EPS bioflocculants with pharmaceutical, environmental and biotechnological implications.