Fatigue is a process of permanent progressive changes in the structure of a material exposed to cyclic loading. High stress ranges in structures like bridges or crane-ways can result into accelerated crack propagation, higher deflections, structural stiffness reduction and consequently into fatigue failure. Bridge decks with damaged or missing insulation, crane-ways in industrial environment, bridge piers adjacent to roads maintained with the use of de-icing salts, maritime structures subjected to wave impact load cycles or cyclic loaded foundations of industrial machinery are exposed to cyclic loading and deteriorative solutions at the same time. In this text, the state-of-art in the field of fatigue of concrete structures is presented together with a brief introduction to deterioration of concrete. On hand of this information a way of describing the strain development under cyclic loading - the fatigue damage function - is proposed and experimentally verified on pre-stressed and reinforced concrete specimens. The way of incorporating the effect of material deterioration in this approach is shown.