A fatigue reliability method has been developed for strain-based fatigue under random loading. The adaptive kernel method is employed to establish the probabilistic random stress model. The probability-based cyclic stress-strain curve considering entire material constants as random variable is proposed. The probabilistic model of cyclic strain life relations is established by introducing a standard normal distribution. Based on these probabilistic models, the random characteristic value of fatigue life is obtained by Monte Carlo method. According to the mean value first order second moment reliability method, the probability of failure can be given out. The example of application is demonstrated.