This paper proposes a modelling approach that combines the discrete element method (DEM) and a novel bonded contact model to characterise the fatigue response of cemented materials. While DEM is commonly used to simulate bonded materials undergoing cracking, the centrepiece of the present method is the development of the novel bonded fatigue model. This new model couples damage mechanics and bounding surface plasticity theory to capture fatigue crack growth in cement bridges between aggregates. Thanks to the incorporation of the bounding surface plasticity, the proposed model provides a smooth transition from static to fatigue damages and vice-versa in a unified manner, making it more flexible to capture damage responses of cemented materials under different loading conditions (i.e. monotonic and cyclic loadings). Moreover, the proposed approach automatically captures the hysteretic response in cement bridges between aggregates under fatigue loadings without ad-hoc treatments. More importantly, by removing the direct dependence of the fatigue damage variable on the number of loading cycles, the modelling approach can be applied to simulate the fatigue behaviour of cemented materials under cyclic variable load amplitudes. The proposed modelling approach is evaluated against several strength tests to examine its predictive capability. Satisfactory agreements with fatigue experiments are achieved for flexural modulus degradations, lifetimes and sensitivity of stress levels under constant and variable amplitude cycles. This result suggests that the proposed discrete modelling approach can be used to conduct numerical experiments for insights into the fatigue behaviour of cemented materials.