Interactions between bacteria and cyanobacteria have been suggested to have a potential to influence harmful algal bloom dynamics; however, little information on these interactions has been reported. In this study, the bacterial communities associated with five strains of Microcystis aeruginosa, three species of other Microcystis spp., and four representative species of non-Microcystis cyanobacteria were compared. Bacterial 16S rDNA fragments were amplified and separated by denaturing gradient gel electrophoresis (DGGE) followed by DNA sequence analysis. The similarities among bacterial communities associated with these cyanobacteria were compared to the digitized DGGE profiles using the cluster analyses. The bacterial community structure of all cyanobacterial cultures differed. Cluster analysis showed that the similarity values among M. aeruginosa cultures were higher than those of other cyanobacterial cultures. Sequence analysis of DGGE fragments indicated the presence of bacteria including, Alphaproteobacteria, Betaproteobacteria, Gammaproteobacteria, Bacteroidetes and Actinobacteria in the cyanobacterial cultures. Members of the Sphingomonadales were the prevalent group among the Microcystis-associated bacteria. The results provided further evidence for species-specific associations between cyanobacteria and heterotrophic bacteria, which are useful for understanding interactions between Microcystis and their associated bacteria.