The three alleles of papG, the Gal(α1-4)Gal-specific adhesin gene of Escherichia coli P fimbriae, were detected in 101 (54%) of 187 E. coli bacteremia isolates from Boston, Long Beach, California, and Nairobi, Kenya, by a polymerase chain reaction-based assay, and their distribution was compared with clonal structure and other bacterial and host characteristics. Allele II predominated overall (57% of papG+ strains, vs. 32% for III and 2% for I). Allele distribution differed significantly between centers. Alleles segregated according to enzyme electrophoretic lineage and O serogroup in patterns suggesting both vertical and horizontal transmission and emergence within E. coli in the temporal sequence II→III→I. Strains containing allele III preferentially agglutinated sheep erythrocytes, whereas strains containing allele II preferentially agglutinated human erythrocytes. Allele III was associated with hly, sfa, multiple copies of the pap operon, and cluster III of the phylogenetic tree. These findings indicate that among bacteremia isolates of E. coli, the three papG alleles exhibit distinctive associations with evolutionary lineages, hemagglutination phenotypes, and non-pap virulence properties.