Backgrounds of local damage detection in composite beams and plates based on measurements of their natural frequencies are presented. The approach can be applied to detection of barely visible damage and damage associated with local environmental effects. The application of the analytical technique discussed in the paper is illustrated for simply supported symmetrically laminated composite beams. It is shown that a local damage occupying a very small volume can be detected using a comparison of natural frequencies of undamaged beams (prior to a possible damage) to their counterparts during the life time of the structure.