For many traits and common human diseases, causal loci uncovered by genetic association studies account for little of the known heritable variation. Such ′ missing heritability ′ may be due to the effect of non-additive interactions between multiple loci, but this has been little explored and difficult to test using existing parametric approaches. We propose a Bayesian non-parametric Gaussian Process Regression model, for identifying associated loci in the presence of interactions of arbitrary order. We analysed 46 quantitative yeast phenotypes and found that over 70% of the total known missing heritability could be explained using common genetic variants, many without significant marginal effects. Additional analysis of an immunological rat phenotype identified a three SNP interaction model providing a significantly better fit (p-value 9.0e-11) than the null model incorporating only the single marginally significant SNP. This new approach, called GPMM, represents a significant advance in approaches to understanding the missing heritability problem with potentially important implications for studies of complex, quantitative traits.