An efficient methodology using static test data and changes in natural frequencies is proposed to identify the damages in structural systems. The methodology consists of two main stages. In the first stage, the Damage Signal Match (DSM) technique is employed to quickly identify the most potentially damaged elements so as to reduce the number of the solution space (solution parameters). In the second stage, a particle swarm optimization (PSO) approach is presented to accurately determine the actual damage extents using the first stage results. One numerical case study by using a planar truss and one experimental case study by using a full-scale steel truss structure are used to verify the proposed hybrid method. The identification results show that the proposed methodology can identify the location and severity of damage with a reasonable level of accuracy, even when practical considerations limit the number of measurements to only a few for a complex structure.