In this paper, an improved GA-based damage detection algorithm using a set of combined modal features is proposed. Firstly, a new GA-based damage detection algorithm is formulated for beam-type structures. A schematic of the GA-based damage detection algorithm is designed and objective functions using several modal features are selected for the algorithm. Secondly, experimental modal tests are performed on free-free beams. Modal features such as natural frequency, mode shape, and modal strain energy are experimentally measured before and after damage in the test beams. Finally, damage detection exercises are performed on the test beam to evaluate the feasibility of the proposed method. Experimental results show that the damage detection is the most accurate when frequency changes combined with modal strain-energy changes are used as the modal features for the proposed method.