A 47 kb genomic island (GEI) bracketed by 50 bp direct repeats, containing 52 annotated genes, was found to delete spontaneously from the genome of Desulfovibrio vulgaris Hildenborough. The island contains genes for site-specific recombinases and transposases, rubredoxin:oxygen oxidoreductase-1 (Roo1) and hybrid cluster protein-1 (Hcp1), which promote survival in air and nitrite stress. The numbering distinguishes these from the Roo2 and Hcp2 homologues for which the genes are located elsewhere in the genome. Cells with and without the island (GEI(+) and GEI(-) cells respectively) were obtained by colony purification. GEI(-) cells arise in anaerobic cultures of colony-purified GEI(+) cells, indicating that the site-specific recombinases encoded by the island actively delete this region. GEI(+) cells survive better in microaerophilic conditions due to the presence of Roo1, whereas the Hcps appear to prevent inhibition by sulfur and polysulfide, which are formed by chemical reaction of sulfide and nitrite. Hence, the island confers resistance to oxygen and nitrite stress. However, GEI(-) cells have a higher growth rate in anaerobic media. Microarrays and enzyme activity stains indicated that the GEI(-) cells have increased expression of genes, which promote anaerobic energy conservation, explaining the higher growth rate. Hence, while lowering the efficiency of anaerobic metabolism, the GEI increases the fitness of D. vulgaris under stress conditions, a feature reminiscent of pathogenicity islands which allow more effective colonization of environments provided by the targeted hosts.