Consortium of bacteria capable of degrading oily hydrocarbons were isolated from tarball on beaches in Terengganu, Malaysia and classified as Pseudomonas stutzeri, Cellulosimicrobium cellulans, Acinetobacter baumannii and Pseudomonas balearica. Taguchi design was used to optimize diesel-oil biodegradation using these bacteria as consortium. Maximum diesel-oil biodegradation by experimental runs was 93.6% with individual n-alkanes degraded between 87.6% – 97.6% in 30 days. Optimal settings were 2.5 mL (1.248 OD600nm) inoculum size; 12% (v/v) initial diesel-oil in minimal salt media with 7.0 pH, 30.0 gL-1 NaCl and 2.0 gL-1 NH4NO3 concentration, incubated at 42oC temperature and 150 rpm agitation speed. Parameters significantly improved diesel-oil removal by consortium as indicated by model determination coefficient (R2 = 90.89%; P < 0.001) with synergistic effect of agitation speed significantly contributing 81.03%. Taguchi design established optimal settings of investigated parameters that produced significant improvement on diesel-oil removal by consortium. This can be used to design novel bioremediation strategy that can achieve optimal decontamination of oil pollution in shorter time.