In this paper we propose a new parameter estimation algorithm for damped sinusoidal signals. Parameter estimation for damped sinusoidal signals with additive white noise is a problem of significant interests in many signal processing applications, such as analysis of NMR data and system identification. The proposed algorithm estimates the signal parameters using a matrix pencil constructed from the measured data. To reduce the noise effect, rank deficient Hankel approximation of prediction matrix is used. We show that the performance of the estimation can be significantly improved by structured low rank approximation of the prediction matrix. Computer simulations also show that the noise threshold of our new matrix pencil algorithm is significantly low than those of the existing algorithms.