Prodigiosin is a natural red pigment with algicidal activity against Cochlodinium polykrikoides, a major harmful red-tide 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, $NaHCO_3$, ${Na}_{2}{SiO}_{3}$, ${NH_4}{NO_3}$, ${Na}_{2}{SO}_{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: 1% sucrose; 0.4% peptone; 0.1 % yeast extract; and (g/l): NaCl, 20.0; ${Na}_{2}{SO}_{4}$, 9.0; $CaCl_2$, 1.71; KCl, 0.4; and (mg/l): ${H_3}{BO_3}$, 10.0; KBr, 50.0; NaF, 2.0; $NaHCO_3$, 45.0; ${Na}_{2}{SiO}_{3}$, 4.5; ${NH_4}{NO_3}$, 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).