Prostate cancer is one of the most common malignancies in males throughout the world, and its incidence is increasing in Asian countries. We carried out a genome-wide association study and replication study using 4,584 Japanese men with prostate cancer and 8,801 control subjects. From the thirty-one associated SNPs reported in previous genome-wide association studies in European populations, we confirmed the association of nine SNPs at P < 1.0 × 10⁻⁷ and ten SNPs at P < 0.05 in the Japanese population. The remaining 12 SNPs showed no association (P > 0.05). In addition, we report here five new loci for prostate cancer susceptibility, at 5p15 (λ-corrected probability P_GC = 3.9 × 10⁻¹⁸), GPRC6A/RFX6 (P_GC = 1.6 × 10⁻¹²), 13q22 (P_GC = 2.8 × 10⁻⁹), C2orf43 (P_GC = 7.5 × 10⁻⁸) and FOXP4 (P_GC = 7.6 × 10⁻⁸). These findings advance our understanding of the genetic basis of prostate carcinogenesis and also highlight the genetic heterogeneity of prostate cancer susceptibility among different ethnic populations.