We consider the problem of estimating the probability of survival (non-failure) and the probability of safe operation (strength greater than a limiting value) of structures subjected to random loads. These probabilities are formulated in terms of the probability distributions of the loads and the material strength. For the material strength, the Weibull distribution is assumed, the parameters of which are estimated by a statistical analysis of the experimental tensile strength of steel specimens subjected to different periods of random loads. The statistical analysis shows that, with the application of random loads, the initial homogeneous distribution of strength changes to a two-component distribution, reflecting the two-stage fatigue damage. In the crack initiation stage, the strength increases initially and then decreases, while an abrupt decrease of strength is seen in the crack propagation stage. The consequences of this behaviour on the fatigue reliability are discussed.