Production of reactive nitrogen species (NO) is a key step in the immune response following infections. NO induces lesions to bacterial DNA, thus limiting bacterial growth within hosts. Using two pathogenic bacteria, Bacillus cereus and Shigella flexneri, we show that the DNA-repair protein Mfd (Mutation-Frequency-Decline) is required for bacterial resistance to the host-NO-response. In both species, a mutant deficient for mfd does not survive to NO, produced in vitro or by phagocytic cells. In vivo, the Delta mfd mutant is avirulent and unable to survive the NO-stress. Moreover, NO induces DNA-double-strand-breaks and point mutations in the Delta mfd mutant. In overall, these observations demonstrate that NO damages bacterial DNA and that Mfd is required to maintain bacterial genomic integrity. This unexpected discovery reveals that Mfd, a typical housekeeping gene, turns out to be a true virulence factor allowing survival and growth of the pathogen in its host, due to its capacity to protect the bacterium against NO, a key molecule of the innate immune defense. As Mfd is widely conserved in the bacterial kingdom, these data highlight a mechanism that may be used by a large spectrum of bacteria to overcome the host immune response and especially the mutagenic properties of NO.