This study presents an efficient approach for the detection of damages in laminated composite beams with arbitrary lay-up. The approach uses the finite element model updating based on limited vibration data and a metaheuristic optimization algorithm. To this aim, a thirteen degrees-of-freedom (DOFs) beam finite element (FE) model is employed for numerical simulation of the actual structure. The Guyan condensation method is employed for model-order reduction to simulate the limited number of sensor data. The damage detection problem is defined as an unconstrained optimization problem. The objective function to be minimized is formulated using the objective function constructed as a weighted linear combination of the root-mean-square error in the frequencies and the error in the correlation between two mode shapes, which is represented by Modal Assurance Criterion (MAC). Teaching-Learning-Based Optimization (TLBO) is used as a metaheuristic tool for optimization. The proposed method is verified by four examples. A parametric study on anisotropic-laminated composite beams with cantilevered and clamped end conditions under three assumed damage scenarios is conducted to show the efficacy of the proposed method. The results indicate that the proposed method can identify single and multiple damages in anisotropic-laminated composite beams with adequate precision and outperforms the other algorithms in terms of accuracy and computational cost.