Oil spill introduces hydrocarbons into the marine environment and forms oil slicks, which aggregate with other debris to form tarballs. Tarballs are composed of toxic hydrocarbons, which persist in the environment, causing economic and ecological damages. This work studied the isolation and optimization of diesel-oil biodegradation by an indigenous bacterium, identified by 16S rRNA gene sequence analysis, in tarball. An experimental methodology using a Taguchi orthogonal array was applied to optimize the effects of diesel concentration, salinity, nitrate concentration, pH, temperature, agitation speed and time. An isolated bacterium identified as Cellulosimicrobium cellulans removed 88.4% of diesel oil under optimized conditions, where initial diesel-oil concentration was 5% (v/v), NaCl concentration was 20 gL-1 and NH4NO3 concentration was 2 gL-1 in Minimal Salt Media at pH 7, 40oC and 100 revolutions per minute for 5 days. Tarballs harbor hydrocarbon-degrading C. cellulans that can be used under optimized conditions to design an effective oil spill bioremediation technique for mitigating oil pollution.