This paper presents a reliability-based prediction methodology to obtain the remaining useful life of composite materials subjected to fatigue degradation. Degradation phenomena such as stiffness reduction and increase in matrix micro cracks density are sequentially estimated through a Bayesian filtering framework that incorporates information from both multi-scale damage models and damage measurements, that are sequentially collected along the process. A set of damage states are further propagated forward in time by simulating the damage progression using the models in the absence of new damage measurements to estimate the time-dependent reliability of the composite material. As a key contribution, the estimation of the remaining useful life is obtained as a probability from the prediction of the time-dependent reliability, whose validity is formally proven using the axioms of Probability Logic. A case study is presented using multi-scale fatigue damage data from a cross-ply carbon-epoxy laminate.