While the DNA damage induced by ionizing radiation and by many chemical compounds and drugs is well characterized, the genotoxic insults inflicted by bacteria are only scarcely documented. However, accumulating evidence indicates that we are exposed to bacterial genotoxins. The prototypes of such bacterial genotoxins are the Cytolethal Distending Toxins (CDTs) produced by Escherichia coli and Salmonella enterica serovar Typhi. CDTs display the DNase structure fold and activity, and induce DNA strand breaks in the intoxicated host cell nuclei. E. coli and certain other Enterobacteriaceae species synthesize another genotoxin, colibactin. Colibactin is a secondary metabolite, a hybrid polyketide/nonribosomal peptide compound synthesized by a complex biosynthetic machinery. In this review, we summarize the current knowledge on CDT and colibactin produced by E. coli and/or Salmonella Typhi. We describe their prevalence, genetic determinants, modes of action, and impact in infectious diseases or gut colonization, and discuss the possible involvement of these genotoxigenic bacteria in cancer.