Damage processes in fatigue loaded concrete structures depend on the number and amplitude of the load cycles applied. Damage evolution is linked to a reduction in concrete stiffness, and it is thought that this reduction causes stress redistributions at component level which have a favourable impact on the service life of a structure. Until now, the stiffness reduction and stress redistribution have never been successfully measured in laboratory tests or in situ. It is only known that the real service life is longer than the calculated one and that indicators of stiffness reduction, such as component deflection, increase with the number of load cycles applied. Ultrasonic measurement techniques are considered to be well suited to detecting degradation processes caused by cyclic loading. It is expected that the stiffness reduction in fatigue loaded concrete structures can be recorded reliably with ultrasonic pulse velocity measurements. In the light of this, fatigue tests were performed on small-scale concrete specimens. The aims of the tests were to understand the correlation between the observed stiffness degradation of the specimens and the results of ultrasonic pulse velocity measurements and to estimate the potential for using ultrasonic pulse velocity measurements in continuous structural health monitoring.