The fatigue cracking of orthotropic steel bridge decks (OSDs) is a difficult problem that hinders the development of steel structures. The most important reasons for the occurrence of fatigue cracking are steadily growing traffic loads and unavoidable truck overloading. Stochastic traffic loading leads to the random propagation behavior of fatigue cracks, which increases the difficulty of the fatigue life evaluations of OSDs. This study developed a computational framework for the fatigue crack propagation of OSDs under stochastic traffic loads based on traffic data and finite element methods. Stochastic traffic load models were established based on site-specific, weigh-in-motion measurements to simulate fatigue stress spectra of welded joints. The influence of the transverse loading positions of the wheel tracks on the stress intensity factor of the crack tip was investigated. The random propagation paths of the crack under stochastic traffic loads were evaluated. Both ascending and descending load spectra were considered in the traffic loading pattern. The numerical results indicated that the maximum value of K_I was 568.18 (MPa·mm^1/2) under the most critical transversal condition of the wheel load. However, the maximum value decreased by 66.4% under the condition of transversal moving by 450 mm. In addition, the propagation angle of the crack tip increased from 0.24° to 0.34°—an increase ratio of 42%. Under the three stochastic load spectra and the simulated wheel loading distributions, the crack propagation range was almost limited to within 10 mm. The migration effect was the most obvious under the descending load spectrum. The research results of this study can provide theoretical and technical support for the fatigue and fatigue reliability evaluation of existing steel bridge decks.