A 5-axis machining method of Non-Uniform Rational B-Spline (NURBS) surface has been proposed in this paper. With the local curvature and the machining error, the step-size was calculated to get the parameter of the next Cutter-Contacting (CC) point. With the method of coordinate transformation, effective machining radius of a flat-end cutter had been deduced and the step-over formed by two adjacent CC paths were implemented. The parameter increment along the CC path interval direction was calculated by using geometric analysis of the local area of CC point. Finally, once all of CC points on the NURBS surface had been obtained, the CC paths for 5-axis surface milling were generated.