Referring to Europe as a whole and to single European countries, previous studies have shown that heavy metal concentrations in mosses (1) are primarily determined by atmospheric deposition of heavy metals; (2) are country and element-specific; and (3) agree well with respect to element-specific spatial patterns and temporal trends of atmospheric deposition of heavy metals. This paper investigates correlations between the concentrations of cadmium, lead and mercury in atmospheric deposition and mosses within the units of an ecological land classification of Europe. To this end, measurements from the 2005/2006 European moss survey and modeled atmospheric deposition in the previous three years were intersected with a map on ecologically defined land classes of Europe. Then, the minimum numbers of sampling sites required within the ecological land classes were computed. Considering spatial auto-correlations, subsequently the correlations between the concentrations of heavy metals in mosses and corresponding deposition were calculated and mapped for each of those ecological land classes containing moss sampling sites. It was concluded that the numbers of sampling sites within Europe and most participating countries as well as within most of the ecological land classes are sufficient for estimating the mean of measurements for the above mentioned three spatial levels within 20% of its true value with 95% confidence. Spatial patterns of correlations between the atmospheric deposition and bioaccumulation were shown to vary by element and ecologically defined land classes.