In order to solve structural multi-damage identification problem, a two-stage method based on Bayesian theory and immune genetic algorithm (IGA) is presented. Firstly, structural modal strain energy and frequency are considered as two kinds of information sources, and Bayesian theory is utilized to integrate the two information sources and preliminarily detect structural damage locations. Then, immune genetic algorithm is used to identify structural damage extents. Considering the convergence rate of basic IGA is still not very good, some improved strategies, such as culture vaccine, two termination conditions, are presented. It is shown that the two-stage method can precisely identify structural damage locations and extent, and the calculated results of the proposed improved IGA are obviously better than those of both the basic IGA and simple genetic algorithm.