An efficient method for time-dependent fatigue reliability assessment of mechanical components under random loadings is proposed. Normally, fatigue damage induced by random loading is high-cycle fatigue problem. The randomness of high-cycle fatigue damage is treated in two aspects. The first one is the uncertainty quantification from the external random loading. The second one is the uncertainty quantification of the fatigue property of the structural component. The former is characterized by Gaussian distribution derived from the rainflow cycle distribution, median stress-life (S-N) curve, and the linear damage accumulation rule. The latter is described with the probabilistic stress-life (P-S-N) curve based on log-normal distribution. The proposed method has colligated these two aspects together to evaluate the expectation and confidence interval of fatigue reliability. Finally, a numerical example is provided to verify the effectiveness of the developed approach. A comparison with bootstrap method is also carried out. The comparative result has shown rational accuracy of the proposed method.