Fatigue damage simulations are computationally demanding due to the high number of simulated load cycles (up to 109 cycles for high-cycle fatigue, HCF) and the non-linear nature of the system of equations in the context of finite element analysis (FEA). For conventional approaches, the Shannon–Nyquist theorem, established in the signal-processing community, prescribes the treatment of damage evolution for cyclic load sequences according to the highest excitation frequency. This requirement results in ex- pensive demands in terms of computation time and data storage for high fidelity FEA models. The compressive sensing (CS) paradigm is widely applied in signal processing for the recovery of full time trajectories from sparse measurements with sub-Nyquist sampling frequencies. For engineering problems, CS approaches and ℓ1-norm minimization techniques for underdetermined systems of equations have emerged for a variety of applications in structural health monitoring, uncertainty modeling under incomplete data, and efficient uncertainty propagation in engineering mechanics. This research focusses on the reduction of computational costs for fatigue damage simulations with the objective of developing a reduced-order model in both space and time. Established non-intrusive POD reduced-basis methods are investigated and applied for spatial model-order reduction. The compressive sensing approach and ℓ1-norm techniques are thoroughly investigated for their ability to circumvent the Shannon–Nyquist theorem and thereby significantly reduce the required number of simulated load cycles. Only individual load cycles are simulated with sparse temporal sampling, and the full damage evolution is recovered by constructing an inverse compressive sensing approach. This project builds upon prior work in reduced-order modeling for fatigue damage simulations that employed cycle-jumping and intrusive LATIN–PGD methods. In contrast, the current research utilizes non-intrusive ROM techniques combined with compressive sensing for sparse recovery to enable fast time-domain predictions of damage evolution under cyclic loading.