The brevetoxin-producing dinoflagellate, Karenia brevis, forms nearly annual blooms off the Florida west coast, severely impacting the region's ecology and economy. Bacteria are often cited as either promoting or interfering with the development of algal blooms, and thus a detailed study of the bacterioplankton assemblages associated with K. brevis was undertaken. We developed sixteen 16S rRNA gene clone libraries from K. brevis bloom and adjacent nonbloom water to determine the bacterial groups present and assess the influence of K. brevis cell number and/or depth on bacterioplankton community composition. Most notably, bacterial groups such as Rhodobacterales (Alphaproteobacteria) and Cytophagales/Sphingobacteriales (Bacteroidetes), reported previously to be associated with other harmful algal species, were often abundant in the presence of K. brevis. Cyanobacteria frequently dominated surface samples containing no detectable K. brevis, consistent with earlier work suggesting that these photosynthetic organisms may be important in promoting the proliferation of these blooms by conditioning the water. Moreover, differences in the abundance/diversity of traditionally more rare and often undocumented phylogenetic groups (e.g. Betaproteobacteria, Deltaproteobacteria, Chloroflexus, Firmicutes) were apparent in bloom vs. nonbloom water. This is the first study to document the association of these phylogenetic groups with natural K. brevis populations and suggests a potential role for these microorganisms in K. brevis bloom dynamics.