Typical civil infrastructures are prone to fatigue-induced failure due to repeated loading during their service life. To effectively manage the consequences of fatigue-induced failure, the remaining useful life (RUL) of a structure must be estimated on the basis of a certain established parameterized fatigue model. Eventually estimation of the pertinent fatigue model parameters becomes imperative which has traditionally been approached offline using a complete available database. This paper proposes an online model-based approach to predict (/estimate) the fatigue life drawing inference from only available structural health monitoring (SHM) data employing an extended Kalman filter (EKF). Keeping the real life uncertainties (loading, model inaccuracy, ambient variability etc.) into account, the study casts the problem in the probabilistic domain. Updated Paris model is employed in this attempt to simulate the fatigue crack growth propagation, and the model parameters are estimated using SHM data while taking the uncertainties into consideration. The proposed method employs two steps: first, to estimate the unknown model parameters using the available crack growth history and the second, to perform the prognosis of the crack based on the estimated model parameters. Numerical studies are conducted on two fracture scenarios: edge and center crack in a finite plate under mechanical and thermal loading conditions. Further, numerical simulations have been carried out to study RUL for a welded joint of a bridge based on its worst operational scenario. To further validate the proposed method, an experimental study is conducted on compact tension (CT) specimens. Estimation of Paris model parameters and fatigue crack prognosis with the proposed approach has been validated on these test sets. This method is observed to be consistently accurate in estimating the fatigue model parameters and subsequently predicting the RUL as well.