With the rapid development of micro-machining technology, the feature size of object parts becomes smaller whilst the roundness tolerance must be critically verified at sub-micrometers or nanometers. Therefore, establishing a method is critically important for evaluating roundness errors to guarantee the machining quality. A progressive search method is proposed based on the minimum zone criterion in the Cartesian coordinate system in this paper. The least-square center of the measured points is used as the initial reference center by establishing a search circle model for progressively approaching the minimum zone circle center. To testify to the feasibility and performance of the proposed method, comparison and simulation experiments are implemented. The results demonstrated that the progressive search method is effective, reliable, and can evaluate roundness error accurately and quickly with not more than 0.1 s and 10 times.