Elastic motion estimation is an effective temporal predictive coding technique of video proposed in recent years. But its optimization solution based on Gauss-Newton method still exhibits the problem of high computational complexity and unstable convergence yet. Thus an elastic motion estimation algorithm is addressed based on an improved Levenberg-Marquardt (L-M) method. First, a fast implementation of the L-M Hessian matrix is designed according to the numerical symmetry of elastic basis function and the Hessian matrix, which reduces its computational complexity by 62.5%. Second, it is found that the update factor of L-M diagonal matrix's damping coefficient has obvious influence on the performance of elastic motion estimation through theoretical and experimental analyses. The squared ratio of the step size in the latest two iterations is used to adaptively determine the update factor, by which the damping coefficient is updated positively and negatively in turn. Experimental results show that the proposed algorithm is able to obtain stable performance for the video sequences with various spatial resolution and scene characteristics. It gains 2.54 dB and 1.77 dB higher average motion-compensated peak signal-to-noise ratio (PSNR) than those of the full search based on block-wise translational model and the elastic motion estimation based on modified Gauss-Newton method, respectively. Furthermore, the proposed algorithm converges fast. Only 1~2 iterations are needed before it achieves higher PSNR than the conventional elastic motion estimation and the block-wise translational full search.