Prodigiosin is a natural red pigment with algicidal activity against Cochlodinium polykrikoides, a major harmful red-tide microalga. To increase the yield of prodigiosin, a mutant of Hahella chejuenesis KCTC 2396, assigned M3349, was developed by an antibiotic mutagenesis using chloramphenicol. When cultured in Sucrose-based Marine Broth medium (SMB), M3349 could produce prodigiosin at 1.628+/-0.06 g/L, while wild type producing at 0.658+/-0.12 g/L under the same conditions. To increase the yield of prodigiosin production by M3349, significant medium components were determined using a two-level Plackett-Burman statistical design technique. Among fourteen components included in SMB medium, NaCl, Na2SiO3, MgCl2, H3BO3, Na2HPO4, Na2SO4, and CaCl2 were determined to be important for prodigiosin production. The medium formulation was finally optimized using a Box-Behnken design as follows: sucrose 10.0, peptone 8.0, yeast extract 2.0, NaCl 10.0, Na2SO4 12.0, CaCl2 1.8, MgCl2 0.7 g/L; and H3BO3 22.0, Na2HPO4 20.0, Na2SiO3 8.0 mg/L. The predicted maximum yield of prodigiosin in the optimized medium was 2.43 g/L by the Box-Behnken design, while the practical production was 2.60+/-0.176 g/L, which was 3.9 times higher than wild type with SMB Medium (0.658 g/L).