This paper presents a probabilistic methodology for model-based fatigue damage prognosis, which also incorporates information from structural health monitoring. This method adopts fracture mechanics-based fatigue crack growth modeling in the predictive prognosis, along with quantification of various sources of uncertainty, such as natural variability, data uncertainty, and model errors. Realtime monitoring data of external variable amplitude loading history is used to construct an adaptive autoregressive integrated moving average (ARIMA) model to predict future loading. A continuous Bayesian updating approach is used to adjust the ARIMA model in accordance with the real-time data. The on-ground crack inspection data on single component or fleet of components is used to quantify the uncertainty in the initial and current size of an existing crack. Bayes' theorem is applied to infer the probability distribution of initial crack size using the inspection results on fleet of components. The cycle-by-cycle simulation of fatigue crack growth is expedited via the use of a surrogate modeling technique (Gaussian process model) to replace computationally expensive finite element analysis. A numerical example, surface cracking in cylindrical components under service loading, is carried out to illustrate the proposed method.