A modified tree seeds algorithm (TSA) was proposed to solve structural stiffness and mass damage identification problems. Firstly, a structure’s acceleration response parameters were used to establish an objective function, and then the TSA with fractional dimension embedded was used to do inversion of the structure’s damages. TSA was a heuristic algorithm with a simple structure and easy to implement. In order to further improve its optimization capacity, a fully new search stage named “search with tree” was introduced. In this stage, a fractional dimension model was introduced to improve the convergence ability in later of TSA. After entering tree seeds stage, two new search modes were used to balance the local search ability and the global search one. A truss structure was taken as a numerical example to obtain its identification results. The results showed that the proposed method can effectively identify a structure’s damage parameters if only limited time domain parameters are known; it is superior to other algorithms and not sensitive to measuring noise.