Azotobacter vinelandii is a soil bacterium related to the Pseudomonas genus that fixes nitrogen under aerobic conditions while simultaneously protecting nitrogenase from oxygen damage. In response to carbon availability, this organism undergoes a simple differentiation process to form cysts that are resistant to drought and other physical and chemical agents. Here we report the complete genome sequence of A. vinelandii DJ, which has a single circular genome of 5,365,318 bp. In order to reconcile an obligate aerobic lifestyle with exquisitely oxygen-sensitive processes, A. vinelandii is specialized in terms of its complement of respiratory proteins. It is able to produce alginate, a polymer that further protects the organism from excess exogenous oxygen, and it has multiple duplications of alginate modification genes, which may alter alginate composition in response to oxygen availability. The genome analysis identified the chromosomal locations of the genes coding for the three known oxygen-sensitive nitrogenases, as well as genes coding for other oxygen-sensitive enzymes, such as carbon monoxide dehydrogenase and formate dehydrogenase. These findings offer new prospects for the wider application of A. vinelandii as a host for the production and characterization of oxygen-sensitive proteins.