Fibre-reinforced composite structures under complex loads exhibit gradual damage behaviour with a degradation of effective mechanical properties and change of their structural dynamic behaviour. Damage manifests itself as spatial increase of inter-fibre failure and delamination-growth, resulting in local changes of stiffness. These changes affect not only the residual strengths but more importantly the structural dynamic behaviour. In case of composite rotors, this can lead to catastrophic failure if an eigenfrequency coincides with the rotational speed. The description and analysis of the gradual damage behaviour of composite rotors therefore provides the fundamentals for a better understanding of unpredicted structural phenomena. The gradual damage behaviour on the example of composite rotors and the resulting damage-dependent dynamic behaviour is experimentally investigated under propagating damage for combined out-of-plane and in-plane loads. A novel observation is reported, where monotonic increase of damage results in non-monotonic frequency shift of significant amount of eigenfrequencies.