Miner’s rule for fatigue damage accumulation does not address conveniently the sequential effects of the fatigue loading due to underloads or overloads though such effects need to be taken into account for specific applications using a convenient model. Non-conservative (unsafe) or over-conservative (non-economic) fatigue predictions may result from such a linear damage analysis. To overcome these limitations, non-linear damage approaches are being proposed in the literature, as for instance, the double linear damage rule (DLDR). Further, advanced probabilistic models, as an alternative to deterministic ones, are being currently applied to fatigue damage assessment under variable (random) amplitude loading, though without including, up to present, sequential effects on the damage accumulation. In this paper, the synergetic effect of applying a non-linear fatigue damage model based on the DLDR in conjunction with a probabilistic approach based on the p-S-N field is pursued allowing the above mentioned sequential effects to be incorporated into a probabilistic damage prediction. The proposed approach was tested with existing fatigue block loading data available for the P355NL1 pressure vessel steel.