To investigate the fatigue performance and fatigue damage process of the Orthotropic Steel Deck (OSD) - Ultra-High Performance Concrete (UHPC) composite bridge deck, a two-span continuous full-scale specimen was designed and tested under cyclic loading. Test results showed that the fatigue cracks firstly initiated near the lower part of the weld toe of the rib-to-cross beam welded joint, and then cracks along the weld length of the U-rib butt-welded joint developed. These observations followed by the OSD-UHPC interface debonding. The U-rib bolted joint exhibited better fatigue resistance than the U-rib butt-welded joint. The S-N curves of the rib-to-cross beam welded joint, the U-rib butt-welded joint and the U-rib bolted joint were established based on existing fatigue test data, and were compared with provisions in design codes. The S-N curves from the beam test for the short-headed stud connectors were compared with that from the push-out test. And the established S-N curves with 95% survival probability from the push-out test could be used to assess the global fatigue performance of the composite deck. Considering the durability-based critical crack width of UHPC, the established tensile S-N curve regarding critical UHPC crack width of 0.05 mm could be used to evaluate the anti-fatigue cracking ability of the UHPC layer in the composite deck system.