The efficiency of CNC machining is greatly influenced by the tool path. A new hybrid algorithm for tool path optimization in CNC varied-shape grinding is presented in this paper. The algorithm was constructed by adding hill-climbing algorithm to nature genetic algorithm. In the new algorithm, the crossover operator and mutation operator were redesigned to enhance the local search capability and to accelerate convergence. Verification experiment demonstrated that the algorithm can reduce non-cutting movement of tool paths and improve machining efficiency significantly.