With the advent of high throughput genetic data, there have been attempts to estimate heritability from genome-wide SNP data on a cohort of distantly related individuals. Linear mixed models (LMMs) are used to estimate this heritability parameter. These LMM approaches assume the total variance to be comprised of genetic and environmental components.  Heritability is the ratio of the genetic variance over the total variance of the trait.  Fitting such an LMM in large-scale cohort studies and estimating these variance parameters, however, is tremendously challenging due to high dimensional linear algebraic operations. In our proposed work, we simplify the LMM by unifying the concept of Genetic Coalescence and Gaussian Predictive Process, thereby greatly alleviating the computational burden.  Our proposed approach PredLMM has much better computational complexity than most of the existing packages and thus, provides an efficient alternative for estimating heritability in large-scale cohort studies.  We illustrate our approach with extensive simulation studies to estimate the heritability of multiple quantitative traits from the UK Biobank cohort.