Uncertainty in structural and machine elements fatigue arises from two main sources. One source resides in the nature of fatigue damage mechanism occurring in engineering materials and the other source sterns from the random nature of operational loading. Under repeated loading, fatigue damage starts at an atomic level, follows through crystalline to microstructure, and appears as macroscopic crack growth damage. This source of uncertainty is evinced by the statistical scatter of fatigue endurance or fatigue strength in tests conduced under virtual identical (standard) conditions. The probabilistic description of scatter arising from fatigue damage mechanism encounters both analytical and computational difficulties. For the purpose of engineering analysis a simplified method is presented in this chapter based on the concept of isoprobable endurance curves, i.e., Wöhler curves associated with a stated probability of failure (Section 2). Under complex varying loading, fatigue analysis requires phenomenological cumulative damage criteria. Both linear (Miner) and a new sequential nonlinear fatigue damage criterion are presented in a probabilistic format (Section 3). The uncertainty source associated with the random nature of operational loading is treated in terms of probabilistic distribution laws of the stress intensity acting in the area where fatigue damage is concentrated, essentially at stress risers (Section 4). Accounting for the both sources of uncertainty an engineering assessment rationale for fatigue endurance prediction is developed. This methodology is now supported by FATDAM, a comprehensive computer code (Section 5). Analytical reliability methods (Section 6) are combined with the basic theory of macroscopic crack propagation (Section 7). This analytical developments accounts in a mean sense for the fatigue crack growth uncertainty. A judicious merge of Monte Carlo simulation of material fatigue crack growth characteristics with the analytical fatigue, reliability methods has been incorporated in FATSIM computer program. Future trends in structural fatigue uncertainty management follow the path of integrating advanced analytical methods of reliability theory with structural materials and field research in the framework of the ever increasing power of computing facilities.