Desert ecosystems are highly fragile to disturbances and their recovery can be decade’s long. Crude oil is a strong environmental pollutant. Under dry conditions and limited nutrients, mainly nitrogen, oil degradation by soil microbial communities.is a challenging task. Creating preferred conditions to promote indigenous microbial biodegradation was previously proven to be effective in treating oil spills in mesic areas. In this study, we looked at the potential of microbial degradation of crude oil components in the soil of a hyper-arid region of the Negev Desert that has recently exposed to a crude oil spill. We looked at microbial community shifts using next-generation sequencing and attempted the isolation of oil-degrading bacterial strains through the establishment of enrichment cultures. Additionally, we looked at the possible role of biocrust-dwelling nitrogen-fixing cyanobacteria in supporting oil degradation by nitrogen supply. Three bacterial strains were isolated from the oil-contaminated soil and were found to carry genes coding for two enzymes involved with crude oil degradation (alkB and NAH). When the oil-contaminated soil was incubated with enrichment cultures of nitrogen-fixing cyanobacteria, established from the same site, an accelerated reduction in petroleum carbon was observed with concurrent accumulation of nitrate, although not higher than the control without addition of nitrogen-fixing cyanobacteria. In the later treatment, however, a graduate increased in nitrogen-fixing cyanobacteria biomass was observed over the incubation time. These results suggest a potential for biological degradation even in the hyper-arid region when enough moisture is available.