A technique is presented for the identification of localized reductions in the stiffness of a structure using natural frequency measurements. The sensitivities of the eigenvalues to localized changes in the stiffness have been developed as a set of underdetermined equations. These equations have been used as the constraints in an optimization problem, which minimizes one of three criteria: (1) the changes in the element stiffnesses; (2) the norm of the changes to the global stiffness matrix; or (3) the residuals of the eigenvalue problem. An additional constraint, which forces the stiffness to always decrease due to damage, places the optimization problem in the realm of nonlinear programming. The overall formulation has provided a useful method to identify damage with a small number of measured natural frequencies. Ten to 90% localized reduction in stiffness was successfully identified in a 10-story, two-bay steel frame. The method was verified using test data from an aluminum, cantilever beam.