An innovative composite deck system has recently been proposed for improved structural performance. To study the fatigue behavior of a steel-concrete composite bridge deck, we took a newly-constructed rail-cum-road steel truss bridge as a case study. The transverse stress history of the bridge deck near the main truss under the action of a standard fatigue vehicle was calculated using finite element analysis. Due to the fact that fatigue provision remains unavailable in the governing code of highway concrete bridges in China, a preliminary fatigue evaluation was conducted according to the fib Model Code. The results indicate that flexural failure of the bridge deck in the transverse negative bending moment region is the controlling fatigue failure mode. The fatigue life associated with the fatigue fracture of steel reinforcement is 56 years. However, while the top surface of the bridge deck concrete near the truss cracks after just six years, the bridge deck performs with fatigue cracks during most of its design service life. Although fatigue capacity is acceptable under design situations, overloading or understrength may increase its risk of failure. The method presented in this work can be applied to similar bridges for preliminary fatigue assessment.