The detection of damage with model-based methods is a constrained nonlinear optimization problem. Conventional optimization approaches usually lead to local minima. Furthermore, they are highly sensitive to experimental noise or numerical errors. Genetic algorithms (GAs) provide an attractive alternative since they can potentially explore the entire solution space and reach the global optimum. However, GAs are inherently slow when they work with complicated or time consuming objective functions. To overcome this problem parallel GAs are proposed, and they are particularly easy to implement and provide a superior numerical performance. In this study, a real-coded parallel GA is implemented to detect structural damage. The objective function is based on operational modal data; it considers the initial errors in the numerical model. False damage detection is avoided by using damage penalization. The algorithm is verified with two experimental cases. First, a test structure of an airplane subjected to three increasing levels of damage. Second, a multiple cracked reinforced concrete beam that is subjected to a nonsymmetrical increasing static load to introduce cracks. In both cases, the detected damage has a good correspondence with the experimental damage.