In order to study the fatigue behavior of the crumb rubber concrete and steel composite beam, six fatigue tests were conducted. This study focused on examining the influence of the rubber particles, shear connection degree, stud diameter and sectional dimension on the fatigue life, accumulated fatigue damage and failure mode. Concrete strain, residual slip, residual deflection and bending stiffness of the composite beams at different loading cycles were measured and analyzed. The test results showed that the plain section assumption cannot be applied to the partial connected composite beams under fatigue loading; the fatigue failure was governed by the shank failure of the studs showing good ductility in the shear span; crumb rubber concrete decreased the crack width and improved the fatigue life effectively; larger residual slip due to the rubber particles improved ductility; larger shear connection degree increased the fatigue life and reduced the shear stiffness degradation; and larger diameter of the studs decreased the fatigue life and ductility. It is shown that this study is helpful for the application of crumb rubber concrete into the composite beams.