Waste materials have a strong potential in the bioremediation of oil-contaminated sites, because of their richness in nutrients and their economical feasibility. We used sewage sludge, soybean meal and wheat straw to biostimulate oil degradation in a heavily contaminated desert soil. While oil degradation was assessed by following the produced CO2 and by using gas chromatography-mass spectrometry (GC-MS), shifts in bacterial community composition were monitored using illumina MiSeq. The addition of sewage sludge and wheat straw to the desert soil stimulated the respiration activities more than the addition of soybean meal. GC-MS analysis revealed that the addition of addition of sewage sludge and wheat straw resulted in 1.7 to 1.8 fold increase in the degraded C14 to C30 alkanes, compared to only 1.3 fold increase in the case of soybean meal addition. The degradation of ≥ 90% of the C14 to C30 alkanes were measured in the soils treated with sewage sludge and wheat straw. MiSeq sequencing revealed that the majority (76.5-86.4% of total sequences) of acquired sequences from the original soil belonged to Alphaproteobacteria, Gammaproteobacteria and Firmicutes. Multivariate analysis of operational taxonomic units (OTUs) placed the bacterial communities of the soils after the treatments in separate clusters (ANOSIM R=0.66, P=0.0001). The most remarkable shift in bacterial communities was in the wheat straw treatment, where 95-98% of the total sequences belonging to Bacilli. We conclude that sewage sludge and wheat straw are useful biostimulating agents for the cleanup of oil-contaminated desert soils.