Pathogenic bacteria experience nitrosative stress from NO generated in the host and from nitrosating species such as S-nitrosoglutathione. The food-borne pathogen Campylobacter jejuni responds by activating gene expression from a small regulon under the control of the NO-sensitive regulator, NssR. Here, we describe the full extent of the S-nitrosoglutathione response using transcriptomic and proteomic analysis of batch- and chemostat-cultured C. jejuni. In addition to the NssR regulon, which includes two hemoglobins (Cgb and Ctb), we identify more than 90 other up-regulated genes, notably those encoding heat shock proteins and proteins involved in oxidative stress tolerance and iron metabolism/transport. Up-regulation of a subset of these genes, including cgb, is also elicited by NO-releasing compounds. Mutation of the iron-responsive regulator Fur results in insensitivity of growth to NO, suggesting that derepression of iron-regulated genes and augmentation of iron acquisition is a physiological response to nitrosative damage. We describe the effect of oxygen availability on nitrosative stress tolerance; cells cultured at higher rates of oxygen diffusion have elevated levels of hemoglobins, are more resistant to inhibition by NO of both growth and respiration, and consume NO more rapidly. The oxygen response is mediated by NssR. Thus, in addition to NO detoxification catalyzed by the hemoglobins Cgb and possibly Ctb, C. jejuni mounts an extensive stress response. We suggest that inhibition of respiration by NO may increase availability of oxygen for Cgb synthesis and function.