In recent years, the migration and transformation of heavy metals (HMs) in soil has become a hot issue. Soil particle size has an important effect on the environmental behavior of HMs in soil. The distribution of HMs in soil is strongly affected by the size of a soil aggregate. In this study, paddy samples in both cultivated and uncultivated soils were collected from Anhui Province, China. The soils were sieved into six particle size fractions (diameters of >4000, 4000−2000, 2000−1000, 1000−250, 250−53, and 4000 μm particles. Moreover, the concentrations of Cd, Cr, Pb, and As were elevated in cultivated paddy soils compared to uncultivated soils. The accumulation of HMs in all paddy soils increased with decreasing particle size. Although the smallest particle size fractions accounted for only 5.65−17.28%, they provided the highest distribution factor (DF) of Cr (1.35), As (1.25), Cd (1.28), and Pb (1.38). The highest contributions of HMs came from the coarser fractions (>2000 μm); however, for Cr, Pb, Cd, and As, the mass loading of <53 μm particles was up to 15.90%, 14.41%, 15.21%, and 15.70%, respectively. The highest content of HMs was found in the finest aggregate, with a pattern of decreasing with increasing aggregate size. In addition, the leachability behaviors of different HMs in different particle size aggregates were different. The leachability behaviors of Cr and Pb in the coarse particle size fractions were the highest, while the leachability behaviors of As and Cd in the less than 250 μm particle size fractions were 10−100 times higher than those of Cr and Pb. A correlation analysis showed that the particle distributions of Fe, TOC, and Mn had significant influences on the distributions of Pb, Cd, As, and Cr. This study provides a theoretical basis for the prevention, treatment, and remediation of HMs pollution in soil.