Estimated breeding values (EBVs) using data from genetic markers can be predicted using a genomic relationship matrix, derived from animal's genotypes, and best linear unbiased prediction. However, if the accuracy of the EBVs is calculated in the usual manner (from the inverse element of the coefficient matrix), it is likely to be overestimated owing to sampling errors in elements of the genomic relationship matrix. We show here that the correct accuracy can be obtained by regressing the relationship matrix towards the pedigree relationship matrix so that it is an unbiased estimate of the relationships at the QTL controlling the trait. This method shows how the accuracy increases as the number of markers used increases because the regression coefficient (of genomic relationship towards pedigree relationship) increases. We also present a deterministic method for predicting the accuracy of such genomic EBVs before data on individual animals are collected. This method estimates the proportion of genetic variance explained by the markers, which is equal to the regression coefficient described above, and the accuracy with which marker effects are estimated. The latter depends on the variance in relationship between pairs of animals, which equals the mean linkage disequilibrium over all pairs of loci. The theory was validated using simulated data and data on fat concentration in the milk of Holstein cattle.