In order to realize the uncertainty evaluation of the workpiece circularity error, the sampling strategy, error evaluation method, and uncertainty of the circular outline of the workpiece were investigated based on the Coordinate Measuring Machine (CMM). First, to achieve many samples from different workpieces, circular outlines were measured. Next, the sample circularity errors were evaluated according to the Differential Evolution (DE) algorithm. Then, by comparing the errors, the adopted sampling strategies and the DE algorithm were explained. Finally, based on the results of the circularity error, the uncertainty was evaluated by applying the GUM and MCM methods. The maximum average difference is 1.1 μm, and the average standard uncertainty of the MCM method is 0.02 μm less than the GUM method. More stable, reliable, and accurate results can be obtained using reasonable sampling points, DE algorithm, and MCM evaluation method.