We investigated the relationship between colibactin-producing (clb+) Escherichia coli and colorectal adenocarcinoma. In total, 729 E. coli colonies were isolated from tumor and surrounding non-tumor regions in resected specimens from 34 Japanese patients; 450 colonies were from tumor regions and 279 from non-tumor regions. clb+ bacteria were found in tumor regions of 11 patients (11/34, 32.4%) and in non-tumor regions of seven of the 11 (7/34, 20.6%). The prevalence of clb+ isolates was 72.7% (327/450) and 44.1% (123/279) in tumor and non-tumor regions, respectively. All the recovered clb+ isolates belonged to the phylogenetic group B2 and were the most predominant type in tumor regions. Hemolytic (α-hemolysin-positive, hlyA+) and non-hemolytic (α-hemolysin-negative, hlyA-) clb+ isolates were obtained from patient #19; however, the prevalence of hlyA+ clb+ isolates was significantly higher in tumor regions (35/43, 81.4%) than in non-tumor regions (3/19, 15.8%). Moreover, a significantly higher production of N-myristoyl-D-asparagine, a byproduct of colibactin biosynthesis, was observed in hlyA+ clb+ isolates than in hlyA- clb+ isolates. Our results suggest that hlyA+ clb+ E. coli may have a selective advantage in colorectal colonization, consequently playing a role in carcinogenesis. The presence of hlyA+ clb+ bacteria in healthy individuals is a risk marker of colorectal cancer.