Klebsiella frequently colonizes the gut and colonization is associated with subsequent infection. To identify genes associated with progression from colonization to infection, we undertook a case-control comparative genomics study. Concordant cases (N = 85), where colonizing and invasive Klebsiella isolates were identical strain types, were matched to asymptomatically colonizing controls (N = 160). Thirty-seven genes were significantly associated with infection, 27 of which remained significant following adjustment for patient variables and bacterial phylogeny. Infection-associated genes were not previously characterized virulence factors, but instead a diverse group of stress resistance, regulatory and antibiotic resistance genes, despite careful adjustment for antibiotic exposure. Many infection-associated genes were plasmid borne, and for some, the relationship with infection was mediated by gut dominance. Five infection-associated genes were validated in a geographically independent cohort of colonized patients. This study identifies novel genes that are reproducibly associated with progression to infection in patients colonized by diverse Klebsiella.