An analysis method based on fractals and wavelet for machined surface profile error was presented. It can be employed to analyze the machined surface in details, and reconstruct the surface profile for doing some related work, such as performance-tolerance analysis and process quality control. The fractal dimension algorithms, the analysis and reconstruction algorithms of surface profile based on wavelets theories were developed. The given example showed that this method and related algorithms were very effective.