The paper presents an effective damage detection method of complex composite structures. It can be carried out through the experimental modal analysis of the damaged structure. The method using the improved Cross Modal Strain Energy (CMSE) technique and Niche GA has many advantages compared with other damage detection methods. The CMSE method can use any modes of the structure and the modes don’t need to be normalized or consistent in scale. The Niche GA improves the efficiency of the calculation and enhances the capacity of identifying structural damage localization. The model is the composite material airfoil case. The numerical results show that the method proposed in this paper is successful for damage detection of complex structures.