Approximately 40 single nucleotide polymorphisms (SNPs) that are associated with prostate cancer (PCa) risk have been identified through genome-wide association studies (GWAS). However, these GWAS-identified PCa risk-associated SNPs can explain only a small proportion of heritability (~13%) of PCa risk. Gene–gene interaction is speculated to be one of the major factors contributing to the so-called missing heritability. To evaluate the gene–gene interaction and PCa risk, we performed a two-stage genome-wide gene–gene interaction scan using a novel statistical approach named “Boolean Operation-based Screening and Testing”. In the first stage, we exhaustively evaluated all pairs of SNP–SNP interactions for ~500,000 SNPs in 1,176 PCa cases and 1,101 control subjects from the National Cancer Institute Cancer Genetic Markers of Susceptibility (CGEMS) study. No SNP–SNP interaction reached a genome-wide significant level of 4.4E–13. The second stage of the study involved evaluation of the top 1,325 pairs of SNP–SNP interactions (P_interaction < 1.0E–08) implicated in CGEMS in another GWAS population of 1,964 PCa cases from the Johns Hopkins Hospital (JHH) and 3,172 control subjects from the Illumina iControl database. Sixteen pairs of SNP–SNP interactions were significant in the JHH population at a P_interaction cutoff of 0.01. However, none of the 16 pairs of SNP–SNP interactions were significant after adjusting for multiple tests. The current study represents one of the first attempts to explore the high-dimensional etiology of PCa on a genome-wide scale. Our results suggested a list of SNP–SNP interactions that can be followed in other replication studies.