Estimation of heritability is fundamental in genetic studies. In recent years, heritability estimation using linear mixed models (LMMs) has gained popularity, because these estimates can be obtained from unrelated individuals collected in genome wide association studies. Typically, heritability estimation under LMMs uses either the maximum likelihood (ML) or the restricted maximum likelihood (REML) approach. Existing methods for the construction of confidence intervals and estimators of standard errors for both ML and REML rely on asymptotic properties. However, these assumptions are often violated due to the bounded parameter space, statistical dependencies, and limited sample size, leading to biased estimates, and inflated or deflated confidence intervals. Here, we show that often the probability that the genetic component is estimated as zero is high even when the true heritability is bounded away from zero, emphasizing the need for accurate confidence intervals. We further show that the estimation of confidence intervals by state-of-the-art methods is highly inaccurate, especially when the true heritability is either relatively low or relatively high. Such biases are present, for example, in estimates of heritability of gene expression in the GTEx study, and of lipid profiles in the LURIC study. We propose a computationally efficient method, Accurate LMM-Based confidence Intervals (ALBI), for the estimation of the distribution of the heritability estimator, and for the construction of accurate confidence intervals. Our method can be used as an add-on to existing methods for heritability and variance components estimation, such as GCTA, FaST-LMM, GEMMA, or EMMA. ALBI is available at http://www.cs.tau.ac.il/~heran/cozygene/software/albi.html.