To study the effect of corrosion on fatigue reliability of stay cables under random traffic and wind load, the fatigue life model for stayed cables considering corrosion is firstly built up based on accelerated corrosion and fatigue performance experimental results for high strength steel wires. Secondly, the fatigue reliability analysis procedure for stay cables under various corrosion levels and time-varying corrosion is established based on the linear cumulative damage theory considering the combination of vehicle and wind load. Finally, the influence of corrosion on fatigue reliability for the stay cable is studied considering the random traffic and wind combined action for a large span cable-stayed bridge. The research results indicate that the down rate of time-varying fatigue reliability increases with the aggravation of corrosion; the corrosion effect on fatigue becomes appreciable when corrosion is higher than level III, particularly for the cables closing to pylon and auxiliary piers; the maximum decreasing amplitude of cable fatigue life are 24% and 44% when corrosion condition changes from zero to level IV and V, respectively; the decrease of time-varying fatigue reliability index under time-varying corrosion is obviously larger than that just corresponding to corrosion level.