Background: This paper aims to investigate the correlations between the concentrations of nine heavy metals in moss and atmospheric deposition within ecological land classes covering Europe. Additionally, it is examined to what extent the statistical relations are affected by the land use around the moss sampling sites. Based on moss data collected in 2010/2011 throughout Europe and data on total atmospheric deposition modelled by two chemical transport models (EMEP MSC-E, LOTOS-EUROS), correlation coefficients between concentrations of heavy metals in moss and in modelled atmospheric deposition were specified for spatial subsamples defined by ecological land classes of Europe (ELCE) as a spatial reference system. Linear discriminant analysis (LDA) and logistic regression (LR) were then used to separate moss sampling sites regarding their contribution to the strength of correlation considering the areal percentage of urban, agricultural and forestry land use around the sampling location. After verification LDA models by LR, LDA models were used to transform spatial information on the land use to maps of potential correlation levels, applicable for future network planning in the European Moss Survey. Results: Correlations between concentrations of heavy metals in moss and in modelled atmospheric deposition were found to be specific for elements and ELCE units. Land use around the sampling sites mainly influences the correlation level. Small radiuses around the sampling sites examined (5 km) are more relevant for Cd, Cu, Ni, and Zn, while the areal percentage of urban and agricultural land use within large radiuses (75–100 km) is more relevant for As, Cr, Hg, Pb, and V. Most valid LDA models pattern with error rates of < 40% were found for As, Cr, Cu, Hg, Pb, and V. Land use-dependent predictions of spatial patterns split up Europe into investigation areas revealing potentially high (= above-average) or low (= below-average) correlation coefficients. Conclusions: LDA is an eligible method identifying and ranking boundary conditions of correlations between atmospheric deposition and respective concentrations of heavy metals in moss and related mapping considering the influence of the land use around moss sampling sites.