Orthotropic steel deck (OSD) in a long-span cable-stayed bridge is vulnerable to fatigue damage at the rib-to-deck (RD) joints due to traffic vehicle load. An algorithm for fatigue damage evaluation simulation of long-span bridge based on mesoscale damage model is presented in this paper. Firstly, the fatigue damage evolution model of steel deck based on microscopic damage mechanics is derived. Combined with the measured traffic data, the random traffic flow simulation is realized based on Monte-Carlo method. Finally, it is applied to estimate the damage accumulation of a multi-span cable-stayed bridge. The results indicate that the fatigue damage accumulation at the rib-to-deck (RD) joints is greater than other areas of the OSD. The cumulative rate of fatigue damage at the rib-to-deck (RD) joints shows a strong nonlinear trend. The results are also compared with those estimated by the linear Miner,s model. The predicted fatigue life is far less than that by the linear Miner,s model.