This work aims to establish a vibration-based damage identification method for fiber-reinforced laminated composites and their sandwich construction. This new on-line structural damage identification technique uses the structural dynamic system reconstruction method exploiting the frequency response functions (FRFs) of a damaged structure. To verify the effectiveness of this damage identification method, the frequency responses obtained by vibration testing of fatigue-damaged laminated composites and honeycomb sandwich beams with debonding are examined according to the extent of the damage via the fatigue-damage load cycle for laminated composites, and via the debonding extent for honeycomb sandwich beams. The changes of the peaks and valley of the FRFs according to the debonding extent and the fatigue load cycles are examined, and the area changes in the FRFs are also discussed as the damage index. The residual FRFs or the difference between intact and damaged FRFs are newly defined for application of the on-line damage identification method. Finally, the delamination extent for the sandwich beams and the fatigue damage level for the laminated composites can be easily identified in terms of the changes in natural frequencies and damping ratios of the reconstructed FRFs for these damaged composite structures.