Blooms of the toxic alga, Pyrodinium bahamense var. compressum (Böhm), have become a problem in Malaysia over the past three decades. The alga is a causative agent of paralytic shellfish poisoning, a potentially fatal neurological disorder. Past research suggest that bacteria-algae association may play a direct or indirect role in toxin production. As such, ribosomal DNA-based restriction enzyme analysis for the identification of bacteria associated with Pyrodinium sps. was undertaken. A total of 16 bacterial isolates were successfully obtained from the clonal cultures of Pyrodinium sps. The diversity of the extracellular bacteria associated with Pyrodinium bahamense var. compressum was limited to the Phyla Proteobacteria and Actinobacteria. The major bacterial species identified included Alcanivorax spp. and Hyphomonas spp., whereas Kocuria spp., Nesterenkonia spp., Alteromonas spp., Roseobacter spp., Xanthomonas spp., and Acinetobacter spp. were identified as minor isolates. The identified bacterium Hyphomonas spp. exhibited high sequence identity with an unknown bacterium strain, SCRIPPS_739, in the GenBank database that is known to be associated with toxic and non-toxic dinoflagellates, Alexandrium spp. and Scrippsiella trochoidea, respectively.