Chronic infection with Helicobacter pylori strains expressing the bacterial oncoprotein CagA confers an increased risk of gastric cancer. While much is known about the ancestry and molecular evolution of Western, East Asian, and Amerindian cagA sequences, relatively little is understood about a fourth group, known as "J-Western," which has been detected mainly in strains from Okinawa, Japan. We show here that J-Western cagA sequences have a more widespread global distribution than previously recognized, occur in strains with multiple different ancestral origins (based on multilocus sequence typing [MLST] analysis), and did not arise recently. As shown by comparisons of Western and J-Western forms of CagA, there are 45 fixed or nearly fixed amino acid differences, and J-Western forms contain a unique 4-amino-acid insertion. The mean nucleotide diversity of synonymous sites (π(s)) is slightly lower in the J-Western group than in the Western and East Asian groups (0.066, 0.086, and 0.083, respectively), which suggests that the three groups have comparable, but not equivalent, effective population sizes. The reduced π(s) of the J-Western group is attributable to ancestral recombination events within the 5' region of cagA. Population genetic analyses suggest that within the cagA region encoding EPIYA motifs, the East Asian group underwent a marked reduction in effective population size compared to the Western and J-Western groups, in association with positive selection. Finally, we show that J-Western cagA sequences are found mainly in strains producing m2 forms of the secreted VacA toxin and propose that these functionally interacting proteins coevolved to optimize the gastric colonization capacity of H. pylori.