Bioremediation, involving biostimulation and/or bioaugmentation, is a promising method to overcome oil spills in Cilacap coastal waters. Cilacap coastal area has high risk on oil pollution. This study investigated the stimulatory effect of nitrogen concentration, bacterial density and the composition of bacterial culture in enhancing oil degradation in this area. The applications of 4 different concentrations of Slow Release Fertilizer (SRF) and 2 different densities of bacterial cells in the form of single (RCO/B/08_008) and mixed culture were employed in microcosm experiments for 28 days. The efficacy of combining bacterial culture and fertilizer application in various concentrations was also tested. Oil degradation, bacterial growth and environmental parameters were monitored periodically during the experiments. The results showed that oil degradation rate was more influenced by nutrient concentration (biostimulation) than bacterial number or culture composition (bioaugmentation) added. The efficacy of biostimulation in degrading oil was better than that of bioaugmentation. Biostimulation increased oil degradation up to 6.4 times higher than the control. The optimum of fertilizer concentration added was 7.5 mg N/g (C:N ratio of 1,000:75), which increased depletion rate both in biostimulation-only and the combination of biostimulation with bioaugmentation up to 6.4 and 7.5 times higher than the control, respectively. It is suggested that bioremediation of oil-contaminated sandy beach in Cilacap would be optimal by employing a combination of Slow Release Fertilizer at concentration having C/N ratio = 1,000 : 75 and RCO/B/08_008 culture at density of 0.5 x 108 cells/mL (100% homology with Alcanivorax sp. TE-9).