The incidence of gastric cancer in Okinawa is lowest in Japan. Some previous reports using small number of strains suggested that the high prevalence of Helicobacter pylori with Western-type cagA in Okinawa compared to other areas in Japan might contribute to the low incidence of gastric cancer. It has still not been confirmed why the prevalence of Western-type cagA strains is high in Okinawa. We examined the association between the virulence factors of H. pylori and gastroduodenal diseases in Okinawa. The genotypes of cagA and vacA of 337 H. pylori strains were determined by PCR and gene sequencing. The genealogy of these Western-type cagA strains in Okinawa was analyzed by multilocus sequence typing (MLST). Overall, 86.4% of the strains possessed cagA: 70.3% were East-Asian type and 16.0% were Western type. After adjustment by age and sex, the presence of East-Asian-type cagA/vacA s1m1 genotypes was significantly associated with gastric cancer compared to gastritis (odds ratio = 6.68, 95% confidence interval = 1.73 to 25.8). The structure of Western-type CagA in Okinawa was different from that of typical Western-type CagA found in Western countries. Intriguingly, MLST analysis revealed that the majority of Western-type cagA strains formed individual clusters but not hpEurope. Overall, low prevalence of gastric cancer in Okinawa may result from the high prevalence of non-East-Asian-type cagA strains. The origin of Western-type cagA strains in Okinawa may be different from those of Western countries.