The potential effects of air pollution are a major concern both in terms of the environment and in relation to human health. In order to support environmental policy, there is a need for accurate measurements of the concentrations of pollutants at high geographical resolution over large regions. However, within such regions, there are likely to be areas where the monitoring information will be sparse and so methods are required to accurately predict concentrations. Set within a Bayesian framework, models are developed which exploit the relationships between pollution and geographical covariate information, such as land use, climate and transport variables together with spatial structure. Candidate models are compared based on their ability to predict a set of validation sites. The chosen model is used to perform large-scale prediction of nitrogen dioxide at a 1×1 km resolution for the entire EU. The models allow probabilistic statements to be made with regard to the levels of air pollution that might be experienced in each area. When combined with population data, such information can be invaluable in informing policy by indicating areas for which improvements may be given priority.