The existent studies on cable stays fatigue for the serviced cable-stayed bridge generally only considered traffic or wind load action respectively. The long span cable-stayed bridges are very sensitive to wind load, so the fatigue estimation of cable stays considering traffic and wind load simultaneously is very important for the bridge safety. In the present research, taking an actual bridge as an example, based on linear cumulative damage theory, fatigue reliability of cable stays is analyzed under combined load of vehicles and wind. Firstly, based on the long-term traffic survey and wind speed data, traffic and wind load probability distribution models for the bridge are built respectively. Secondly, an intensive computational work is performed to obtain stress time history of the stay cables in the typical time block by running self-compiled Bridge-Vehicle-Wind interaction dynamic response analysis program. Thirdly, the stress result is updated in accordance with traffic growth and extreme wind speed changing in service period. The stress amplitude and frequency are attained by rain-flow cycle counting method. Finally, the fatigue damage limit state function of cable stays is proposed based on linear cumulative damage theory, and solved by Monte-Carlo method. The analysis result shows that the effect of buffeting wind load on the fatigue reliability of cable stays is significant, the influence degree increases generally in accordance with the order from short cable to long cable. The fatigue life of cable under designed safety probability reduces by the range from 2% to 63%, average 50% compared to only considering traffic load. So fatigue assessment of stay cables should take traffic and wind loads together into account. The proposed analysis framework offers a referenced fatigue assessment approach for conventional long span bridges.