Using agricultural topsoil samples from 641 sites in Guangzhou collected in 2005 and methods of geo-statistics and multi-scale nested model, we characterized the scale effect of spatial structure of heavy metals of Cd and Pb in agricultural soils on three scales and projected their spatial distributions. The results showed that the spatial dependence decreased from coarser to fine grained scales, while the representation of semivariance improved increase with changing scales correspondingly. The spatial interpolation accuracy of Cd and Pb using the multi-scale nested model was in totally higher than that using the ordinary Kriging at a single scale. The multi-scale nested model estimated that the majority of agricultural soils in Guangzhou were uncontaminated compared with the Grade Ⅱ national standard for heavy metal concentration in agricultural soils, of which 7.64% were polluted by Cd primarily located in vegetable fields near the most densely populated area (i.e. city center) and probably due to traffic activities, chemical fertilizer and sewage irrigation.