It is becoming increasingly evident that single-locus effects cannot explain complex multifactorial human diseases like cancer. We applied the multi-factor dimensionality reduction (MDR) method to a large cohort study on gene-environment and gene-gene interactions. The study (case-control nested in the EPIC cohort) was established to investigate molecular changes and genetic susceptibility in relation to air pollution and environmental tobacco smoke (ETS) in non-smokers. We have analyzed 757 controls and 409 cases with bladder cancer (n = 124), lung cancer (n = 116) and myeloid leukemia (n = 169). Thirty-six gene variants (DNA repair and metabolic genes) and three environmental exposure variables (measures of air pollution and ETS at home and at work) were analyzed. Interactions were assessed by prediction error percentage and cross-validation consistency (CVC) frequency. For lung cancer, the best model was given by a significant gene-environment association between the base excision repair (BER) XRCC1-Arg399Gln polymorphism, the double-strand break repair (DSBR) BRCA2-Asn372His polymorphism and the exposure variable 'distance from heavy traffic road', an indirect and robust indicator of air pollution (mean prediction error of 26%, P < 0.001, mean CVC of 6.60, P = 0.02). For bladder cancer, we found a significant 4-loci association between the BER APE1-Asp148Glu polymorphism, the DSBR RAD52-3′-untranslated region (3′-UTR) polymorphism and the metabolic gene polymorphisms COMT-Val158Met and MTHFR-677C > T (mean prediction error of 22%, P < 0.001, mean CVC consistency of 7.40, P < 0.037). For leukemia, a 3-loci model including RAD52-2259C > T, MnSOD-Ala9Val and CYP1A1-Ile462Val had a minimum prediction error of 31% (P < 0.001) and a maximum CVC of 4.40 (P = 0.086). The MDR method seems promising, because it provides a limited number of statistically stable interactions; however, the biological interpretation remains to be understood.