Vibration-based damage identification can constitute a successful approach for Structural Health Monitoring (SHM) of civil structures. It is a non-destructive condition assessment method, dependent on the identification of changes in the modal characteristics of a structure that are related to damage. However, the damage identification from the modal characteristics of existing structures currently suffers from a low sensitivity of eigenfrequencies and mode shapes to certain types of damage. Furthermore, the sensitivity of eigenfrequencies to environmental influences may be sufficiently high to completely mask the effect even of severe damage. Modal strains and curvatures are more sensitive to local damage, but the direct monitoring of these quantities is challenging when the strain level is very low. In the present work, the identification of the modal strains of a pre-stressed concrete beam, subjected to a progressive damage test, is performed. Dynamic measurements are conducted on the beam at the beginning of each cycle and its response is recorded with multiplexed Fiber-optic Bragg Grating (FBG) strain sensors. Bending, lateral and torsional modes are accurately identified from dynamic strains of the sub-microstrain level. The evolution of the modal characteristics of the beam after each loading cycle is investigated. Changes of the eigenfrequency values, the amplitude and the curvature of the strain mode shapes are observed. The changes in the strain mode shapes appear at the locations where the damage is induced, and are already identified from an early damaged state.