This paper introduced fractal theory to the description of gradation of asphalt mixture. The feasibility of description of RAP gradation by fractal theory was firstly discussed. The fractal dimension calculated by Least Square Method (LSM) was employed to evaluate gradation of RAP. Compaction tests, surface-dry condition method tests and indirect tensile strength tests were then employed to evaluate physical and mechanical performance of RAP mixtures stabilized by foamed asphalt. Relationships between fractal dimension and test results were studied. It seems that the fractal dimensions are of relevance to the performance of cold-recycling asphalt mixture. And this points out a new direction of RAP research field.