Prodigiosin is a natural red pigment with algicidal activity against Cochlodinium polykrikoides, a major harmful redtide microalga. To increase the yield of prodigiosin production by Hahella chejuensis KCTC 2396, significant medium components were determined using a two-level Plackett- Burman statistical design technique. Among 12 components included in basal medium, NaHCO3, Na2SiO3, NH4NO3, Na2SO4, and CaCl2 were determined to be important for prodigiosin production. The medium formulation was finally optimized using a Box-Behnken design as follows: 1% sucrose; 0.4% peptone; 0.1% yeast extract; and (g/l): NaCl, 20.0; Na2SO4, 9.0; CaCl2, 1.71; KCl, 0.4; and (mg/l): H3BO3, 10.0; KBr, 50.0; NaF, 2.0; NaHCO3, 45.0; Na2SiO3, 4.5; NH4NO3, 4.5. The predicted maximum yield of prodigiosin in the optimized medium was 1.198 g/l by the Box-Behnken design, whereas the practical production was 1.495 g/l, which was three times higher than the basal medium (0.492 g/l).