Finding gene interaction models is one of the most important issues in genotype-phenotype association studies. This paper presents a model-free nonparametric statistical interaction analysis known as Parallel Haplotype Configuration Reduction (pHCR). This technique extends the original Multifactor Dimensionality Reduction (MDR) algorithm by using haplotype contribution values (c-values) and a haplotype interaction scheme instead of analyzing interactions among single-nucleotide polymorphisms. The proposed algorithm uses the statistical power of haplotypes to obtain a gene-gene interaction model. pHCR computes a statistical value for each haplotype, which contributes to the phenotype, and then performs haplotype interaction analysis on the basis of the cumulative c-value of each individual haplotype. To address the high computational complexity of pHCR, this paper also presents a scalable parallel computing solution. Nine common two-locus disease models were used to evaluate the algorithm performance under different scenarios. The results from all cases showed that pHCR shows higher power to detect gene-gene interaction in comparison with the results obtained from running MDR on the same data set. We also compared pHCR with FAMHAP, which mainly considers haplotype in the association analysis. For every experiment on the simulated data set, pHCR correctly produced haplotype interactions with much fewer false positives. We also challenged pHCR with a real data set input of beta-thalassemia/Hemoglobin E (HbE) disease. The result suggested the interaction between two previously reported quantitative trait loci of the fetal hemoglobin level, which is a major modifying factor, and disease severity of beta-thalassemia/HbE disease.