For non-linear systems the estimation of fatigue damage under stochastic loadings can be rather time-consuming. Usually Monte Carlo simulation (MCS) is applied, but the coefficient-of-variation (COV) can be large if only a small set of simulations can be done due to otherwise excessive CPU time. The reason is that the fatigue damage estimation is very sensitive to the largest values from the simulations. The paper suggests the additional use of the First Order Reliability Method (FORM) to get a better estimation of the tail in the distribution of the estimated fatigue damage and thereby reducing the COV. For a specific example dealing with stresses in a tendon in a tension leg platform the COV is thereby reduced by a factor of three.