To deal with over-shooting and gouging in high speed machining, a novel approach for velocity smooth link is proposed. Considering discrete tool path, cubic spline curve fitting is used to find dangerous points, and according to spatial geometric properties of tool path and the kinematics theory, maximum optimal velocities at dangerous points are obtained. Based on method of velocity control characteristics stored in control system, a fast algorithm for velocity smooth link is analyzed and formulated. On-line implementation results show that the proposed approach makes velocity changing more smoothly compared with traditional velocity control methods and improves productivity greatly.