This study focuses on characterizing the fatigue damage accumulated in nonlinear aeroelastic systems subjected to stochastic inflows through both numerical simulations and wind tunnel experiments. In the mathematical model, nonlinearities are assumed to exist either in the structure (via a cubic hardening nonlinearity in the pitch stiffness), or in the flow (via dynamic stall condition), or simultaneously in both the structural and aerodynamic counterparts. The aerodynamic loads in the attached flow and dynamic stall conditions are estimated using Wagner's formulation and semi-empirical Leishman–Beddoes model, respectively. To augment the findings to in-field flow conditions, the oncoming wind flow is considered to be randomly time-varying in nature. The stochastic input flow fluctuations are modeled using a Karhunen–Loeve Expansion formulation. The response dynamics and the associated fatigue damage of the aeroelastic system, possessing different sources of nonlinearities, are systematically investigated under isolated cases of deterministic and stochastic input flows. Specifically, the pertinent role of stochasticity in the input flow is brought out by presenting the response dynamics and the associated fatigue damage accumulation for different values of noise intensity and time scale of the input flow fluctuation. It is demonstrated that under fluctuating flow conditions, the dynamics intermittently switch between attached flow and the dynamic stall regimes even at low mean flow speeds. The intermittent nature of the response varies as the time scale and intensity of the oncoming flow are varied. The role of torsional stresses as the predominant component dictating the fatigue damage accumulation irrespective of the source of nonlinearity is illustrated. Using the rainflow counting method and Miner's linear damage accumulation theory, it is shown that the accumulated fatigue damage is substantially higher under stochastic flow conditions as compared to deterministic input flows. Importantly, it is observed that different time scales and intensities of the oncoming flow fluctuation play a pivotal role in dictating the fatigue damage in aeroelastic systems. Finally, fatigue damage is observed to be significantly higher for torsionally dominant oscillations in the dynamical stall regime compared to the oscillations at the attached flow regime. The numerical findings are strengthened by drawing comparisons with the preliminary results obtained from wind tunnel experiments performed on a NACA 0012 airfoil undergoing dynamic stall. To the best of our knowledge, this is the first study that systematically bridges the dichotomy between the stall-induced dynamical signatures in stochastic aeroelastic systems and maps the same to the corresponding structural damage. © 2022 Elsevier Ltd