A consortium of bacteria capable of decomposing oily hydrocarbons was isolated from tarballs on the beaches of Terengganu, Malaysia, and classified as Pseudomonas stutzeri, Cellulosimicrobium cellulans, Acinetobacter baumannii and Pseudomonas balearica. The Taguchi design was used to optimize the biodegradation of diesel using these bacteria as a consortium. The highest biodegradation of diesel-oil in the experimental tests was 93.6%, and the individual n-alkanes decomposed 87.6—97.6% over 30 days. Optimal settings were inoculum size of 2.5 mL (1.248 OD600nm); 12% (v/v) the initial diesel-oil in a minimal salt medium of pH 7.0, 30.0 gL−1 NaCl and 2.0 gL−1 NH4NO3 concentration, incubated at 42 °C temperature and 150 rpm agitation speed. Parameters significantly improved diesel-oil removal by consortium as shown by the model determination coefficient (R2 = 90.89%; P < 0.001) with a synergistic effect of agitation speed significantly contributing 81.03%. Taguchi design determined the optimal settings for the parameters under study, which significantly improved diesel-oil removal by consortium. This can be used to design a novel bioremediation strategy that can achieve optimal decontamination of oil pollution in a shorter time. Highlights: Hydrocarbon-degraders in Tarball were isolated and identified by their 16S rRNA gene sequence as Pseudomonas stutzeri, Cellulosimicrobium cellulans, Acinetobacter baumanniiand Pseudomonas balearica. Taguchi method was applied to optimize effects of parameters such as initial diesel concentration, salinity (NaCl concentration), nitrate (NH4NO3) concentration, pH, temperature, agitation speed and inoculum size on diesel-oil removal in 30 days. 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 MSM media with 7.0 pH, 30.0 gL−1 NaCl and 2.0 gL−1 NH4NO3 concentration, incubated at 42 °C temperature and 150 rpm agitation speed Parameters significantly improved diesel-oil removal by this 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 [ABSTRACT FROM AUTHOR]