Harmful algal blooms (HABs or red tides), caused by uncontrolled proliferation of marine phytoplankton, impose a severe environmental problem and occasionally threaten even public health. We sequenced the genome of an EPS-producing marine bacterium Hahella chejuensis that produces a red pigment with the lytic activity against red-tide dinoflagellates at parts per billion level. H. chejuensis is the first sequenced species among algicidal bacteria as well as in the order Oceanospirillales. Sequence analysis indicated a distant relationship to the Pseudomonas group. Its 7.2-megabase genome encodes basic metabolic functions and a large number of proteins involved in regulation or transport. One of the prominent features of the H. chejuensis genome is a multitude of genes of functional equivalence or of possible foreign origin. A significant proportion (${sim}23%$) of the genome appears to be of foreign origin, i.e. genomic islands, which encode genes for biosynthesis of exopolysaccharides, toxins, polyketides or non-ribosomal peptides, iron utilization, motility, type III protein secretion and pigment production. Molecular structure of the algicidal pigment was determined to be prodigiosin by LC-ESI-MS/MS and NMR analyses. The genomics-based research on H. chejuensis opens a new possibility for controlling algal blooms by exploiting biotic interactions in the natural environment and provides a model in marine bioprospecting through genome research.