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${pm}$0.06 g/L, while wild type producing at 0.658${pm}$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, $Na_2SiO_3,;MgCl_2,;H_3BO_3,;Na_2HPO_4,;Na_2SO_4,;and;CaCl_2$ 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, $Na_2SO_4;12.0,;CaCl_2;1.8,;MgCl_2;0.7g/L;;and;H_3BO_3;22.0;Na_2HPO_4;20.0,;Na_2SiO_3;8.0mg/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${pm}$0.176 g/L, which was 3.9 times higher than wild type with SMB Medium (0.658 g/L).