The implementation and maintenance of an air pollution monitoring program can be expensive and time consuming, especially when the aim is for long-term monitoring over a significant area. Consequently, it is essential that sites are optimized to provide the best representative cover while minimizing costs. In the past, there has been a tendency to locate sampling stations at pollution hot-spots. While this is acceptable for determining a maximum potential exposure or identifying the extent of a risk, there are limitations to this approach when assessing the potential impact of any future abatement strategies or determining the level of exposure outside the vicinity. This paper presents an approach in which representative air quality assessments can be undertaken for an urban area using the minimum number of measurement sites. A novel methodology is described that involves site selection to capture the maximum variance in measured pollutants, while minimizing spatiotemporal autocorrelation between the selected sites. A case study is presented for Yazd, Iran. Overall, the results show that the proposed methodology can be effective and enable the long-term monitoring of air pollution to be undertaken on a cost-effective basis in urban areas. In addition, there is the potential for the methodology to be utilized for other forms of pollution (e.g., water, soil, and noise).