This paper presents push-out tests of stud shear connectors to examine their fatigue behavior for developing a new composite bridge deck system. The fifteen push-out specimens of D16 mm stud welded on 9 mm steel plate were fabricated according to Eurocode-4, and a series of fatigue endurance test and residual strength test were performed. Additionally, the stiffness and strength variations by cyclic loading were compared. The push-out test, when the stiffness reduction ratio of the specimens was 0.95 under cyclic load, resulted in the failure of the studs. The stiffness variation of the push-out specimens additionally showed that the application of cyclic loads reduced the residual strength. The fatigue strength of the shear connectors were compared with the design values specified in the Eurocode-4, ASSHTO LRFD and JSSC codes. The comparison result showed that the fatigue endurance of the specimens satisfies the design values of these codes.