Harmful algal blooms, caused by rapid growth and accumulation of certain microalgae in the ocean, pose considerable impacts on marine environments, aquatic industries and even public health. Here, we present the 7.2-megabase genome of the marine bacterium Hahella chejuensis including genes responsible for the biosynthesis of a pigment which has the lytic activity against a red-tide dinoflagellate. H.chejuensis is the first sequenced species in the Oceanospiralles clade, and sequence analysis revealed its distant relationship to the Pseudomonas group. The genome was well equipped with genes for basic metabolic capabilities and contained a large number of genes involved in regulation or transport as well as with characteristics as a marine heterotroph. Sequence analysis also revealed a multitude of genes of functional equivalence or of possible foreign origin. Functions encoded in the genomic islands include biosynthesis of exopolysacchrides, toxins, polyketides or non-ribosomal peptides, iron utilization, motility, type III protein secretion and pigmentation. Molecular structure of the algicidal pigment, which was determined through LC-ESI-MS/MS and NMR analyses, indicated that it is prodigiosin. In conclusion, our work provides new insights into mitigating algal blooms in addition to genetic make-up, physiology, biotic interactions and biological roles in the community of a marine bacterium.