It is difficult to achieve trajectory planning and automatic programming for the remanufacturing of complex shaft shaped part. Aiming at this case, reverse measurement was completed based on non uniform rational B-spline(NURBS) curve for surface of part. A constant arc increment interpolation method was presented for laser cladding remanufacturing and the Newton iteration algorithm based on Romberg integral method was proposed and designed. A program based on 6 DOF robot was developed for trajectory planning and computer aided programming. The morphology, microstructure, thickness and micro-hardness of layer were tested and analyzed. It is observed that, the cladding layer and substrate have a good metallurgical bond, layer thickness is uniform, when the max laser beam tilt angle from the horizontal is 42°, cladding thickness decreases 0.034 mm compared with maximum thickness, the micro-hardness is significantly higher than the substrate. Experimental results show the effectiveness of the method proposed.