In stepped-frequency radar, the contrast cost function can be used to estimate the target radial velocity and acceleration, and therefore reduce range profile distortions. However, the contrast cost surface fluctuates sharply in the velocity and acceleration space, which greatly limits the efficiency of the algorithm. In this study, the cause of this fluctuation is analyzed and its elimination is formulated analytically through strict formula derivation. Based on intensive study of the inherent properties of the contrast cost surface, a novel and highly efficient target motion compensation algorithm is presented. Theoretical analysis and simulations confirm the effectiveness and feasibility of this new algorithm.