Artificial Bee Colony (ABC) Algorithm has received much attention because of its simplicity in parameter tuning and efficiency in modelling. In this paper, a heuristic algorithm fusing niche identification (NIT) with ABC technique is developed to solve multimodal optimization problems and is then applied for structural damage identification. The Depth First Search (DFS) is adopted to improve the accuracy of detection results, and a new particle update scheme is proposed to maintain the diversity of particle populations. The effectiveness and robustness of the algorithm are demonstrated by the well-known benchmark functions and case studies. Results show that, even for the contaminated data and complex damage scenarios, a better identification performance can be achieved using the DFS-based NIT with ABC optimization algorithm.