In health monitoring of civil structures, it is an important task to on-line detect the instant, location and degree of structural damage based on limited structure dynamic responses when disaster occurs. In this paper, a damage detection approach is proposed for on-line tracking and detecting the abrupt degradations of structural stiffness using partial measurements of structural acceleration responses. The main idea of the proposed approach is to identify structural stiffness parameters based on Extended Kalman Filter first, and detect the time instant of abrupt change of structural stiffness parameters based on deviation of the quadratic sum of observed and predicted acceleration responses. The exact locations and extents of structural damages are determined by optimizing the change of structural stiffness parameters. Both a numerical example and an experimental verification demonstrate that the proposed approach is able to on-line detect the time instant, location and degree of structural damage due to the abrupt degradation of structural stiffness.