In the whole lifetime of structures, fatigue damage accumulation will exist in the shear connector of steel–concrete composite beams. It is essential to determine the residual mechanical properties of shear connectors under long-term fatigue loads, e.g., the vehicle load on bridges. In this regard, a shear-strength degradation model is proposed for shear connectors. The Bayes theorem is used to develop posterior estimates of the unknown parameters in the degradation model based on the collected pushout test data of pre-damaged stud connectors caused by high-cycle fatigue loads. In addition, according to the proposed shear-strength degradation model, the service reliability assessment is performed with a composite bridge beam. The results indicate that (1) There is a large diversion in the traditional strength degradation model under the action of fatigue cumulative damage. More importantly, this proposed physics-based degradation model can effectively reduce uncertainty. (2) The effects of steel type and test specimen size can be well considered in the proposed shear-strength degradation model, which is beneficial for improving the reliability of risk assessment for fatigued bridges.