Satellite aerosol products have been widely used to retrieve ground PM concentration because of their wide coverage and continuous spatial distribution. While more and more studies have focused on the retrieval algorithms, the foundation for the retrieval-relationship between PM and satellite aerosol optical depth (AOD) has not been fully investigated. In this study, the relationships between PM and AOD were investigated in 368 cities in mainland China from February 2013 to December 2017, at different temporal and regional scales. Pearson correlation coefficients and the PM/AOD ratio were used as indicators. Firstly, we established the relationship between PM and AOD in terms of the spatio-temporal variations, and discuss the impact of some potential factors for a better understanding of the spatio-temporal variations. Spatially, we found that the correlation is higher in the Beijing-Tianjin-Hebei and Chengyu regions and weaker in coastal areas. The PM/AOD ratio shows an obvious north-south difference, with the ratio in North China higher than South China. Temporally, the correlation coefficient tends to be higher in May and September, with the PM/AOD ratio higher in winter and lower in summer. As for interannual variations, we detected a decreasing tendency for the PM-AOD correlation and PM/AOD ratio for recent years. Then, to determine the impact of the weakening of the PM-AOD relationship on PM remote sensing retrieval performance, a geographically weighted regression (GWR) retrieval experiment was conducted. The results showed that the performance of retrievals is also decreasing while PM-AOD relationship getting weaker. Our study investigated the PM-AOD relationship over a large extent at the city scale, and investigated the temporal variations in terms of interannual variations. The results will be useful for the satellite retrieval of PM concentration and will help us to further understand the PM pollution situation in mainland China.