Ingested Vibrio cholerae pass through the stomach and colonize the small intestines of its host. Here, we show that V. cholerae requires at least two types of DNA repair systems to efficiently compete for colonization of the infant mouse intestine. These results show that V. cholerae experiences increased DNA damage in the murine gastrointestinal tract. Agreeing with this, we show that passage through the murine gut increases the mutation frequency of V. cholerae compared to liquid culture passage. Our genetic analysis identifies known and novel defense enzymes required for detoxifying reactive nitrogen species (but not reactive oxygen species) that are also required for V. cholerae to efficiently colonize the infant mouse intestine, pointing to reactive nitrogen species as the potential cause of DNA damage. We demonstrate that potential reactive nitrogen species deleterious for V. cholerae are not generated by host inducible nitric oxide synthase (iNOS) activity and instead may be derived from acidified nitrite in the stomach. Agreeing with this hypothesis, we show that strains deficient in DNA repair or reactive nitrogen species defense that are defective in intestinal colonization have decreased growth or increased mutation frequency in acidified nitrite containing media. Moreover, we demonstrate that neutralizing stomach acid rescues the colonization defect of the DNA repair and reactive nitrogen species defense defective mutants suggesting a common defense pathway for these mutants.