Fatigue　of　heavy-haul　railway　bridges　has　been　an　ongoing　concern　due　to　the　excessive　stresses　and　frequent　cyclic　effects　of　freight　trains.　Current　fracture-based　fatigue　research,　which　promotes　fatigue　reliability　analysis　caused　by　crack　propagation,　is　challenged　by　the　dilemma　between　the　detailed　modeling　of　cyclic　stress　and　the　reflection　of　temporal　characteristics　of　loading　conditions.　In　addition,　due　to　the　strong　non-Gaussian　nature　of　the　fatigue　limit　state　function　and　the　computational　inefficiency　of　integrating　finite　element　analysis,　current　time-dependent　reliability　methods　need　to　be　further　developed.　To　evaluate　the　fatigue　reliability　of　heavyhaul　railway　steel　bridges　considering　the　temporal　dependence　of　cyclic　train　loading,　a　time-dependent　fatigue　reliability　methodology　is　developed　in　this　study　with　two　innovations.　Firstly,　a　cyclic　stress　range　model　is　proposed　based　on　the　load　analysis　at　the　bridge　level,　which　can　capture　the　time-dependent　characteristics　of　the　incurred　stress　range　throughout　service　life.　Then,　an　improved　outcrossing　rate　method　for　strong　nonGaussian　fatigue　limit　state　functions　is　developed　to　reduce　the　computational　costs　associated　with　reliability　analysis　integrated　with　the　finite　element　model.　The　developed　time-dependent　fatigue　reliability　methodology　is　then　applied　to　a　heavy-haul　railway　steel　truss　bridge　located　in　Shandong,　China,　which　proves　its　efficiency　and　accuracy　in　evaluating　the　time-dependent　fatigue　reliability　of　heavy-haul　railway　steel　bridges.　Furthermore,　the　developed　methodology　is　able　to　provide　insight　into　the　balance　between　bridge　fatigue　damage　and　freight　volume,　and　it　is　found　that　the　combination　of　small　train　axle　weight　and　high　operation　frequency　is　the　optimal　solution　to　achieve　the　fatigue　reliability　of　the　steel　bridge　while　fulfilling　the　freight　demand.