The elasto-plastic contact models of cylinder-based and sphere-based fractal rough surfaces are developed. In the two models, the critical contact areas of a single asperity are scale-dependent. With an increase in the contact load and contact area, a transition from elastic, elasto-plastic to full plastic deformation takes place in this order. The truncated asperity size distribution functions of different frequency indexes in different contact zones are deduced. The relations between the total real contact area and total contact load for cylinder-based and sphere-based fractal rough surfaces are obtained. The pressure distributions in the contact zone are obtained. The results of elasto-plastic contact models show that the mechanical property of cylinder-based and sphere-based fractal rough surfaces depends on the range of the frequency index of asperities. When the first six frequency indexes are smaller than the elastic critical frequency index, the cylinder-based and sphere-based fractal rough surfaces approximately appear to have an elastic property in the complete contact process. When the minimum frequency index is greater than the elastic critical frequency index, elastic deformation first takes place in the rough surfaces. Then, elasto-plastic deformation takes place with an increase in the total contact load. In elastic deformation, the ratios of the peak pressures of present fractal models to those of Hertzian models are constant for a given range of frequency indexes. In inelastic deformation, the ratios of the peak pressures are inversely proportional to the total contact load.