Abstract: To find the optimal vibration sensor placement (OVSP) during designing a structural health monitoring system, the gradation-immune firefly algorithm (GIFA) was proposed by introducing the gradation strategy and the immune pattern to improve the original firefly algorithm. The dual-structure coding method was employed to overcome the shortage that the original firefly algorithm can only be applied to optimal problems with continuous variables. The gradation strategy was developed to limit individuals with different gradations in their respective search space. As a result, the diversity of population is ensured and the individuals with good performance are inherited. Furthermore, the immune pattern is utilized to perform selecting, memorizing, crossing and mutating for fireflies and enhance the capability of global searching and local optimization of the GIFA. A full-scale benchmark cable-stayed bridge was employed as a case study. The parametric sensitivity of the proposed GIFA was discussed and the optimal sensor configurations were offered. The results indicate that the computational efficiency of the GIFA and the quality of optimal solutions provided by the GIFA are dramatically improved when comparing with the simple discrete firefly algorithm. The GIFA is an excellent approach to solve OVSP problems.