To study the shear behavior and competitive failure mechanisms of headed stud connectors in steel-concrete composite structures under the influence of freeze-thaw cycles (FTCs), the material performance test of C60 concrete after FTCs and push-out tests of 36 miniaturized specimens of headed stud connectors under FTCs were carried out. The cubic compressive strength, dynamic elastic modulus, and mass loss rate of C60 concrete were obtained after different FTCs. Failure modes, load-slip curve, shear capacity, and shear stiffness of stud connectors were investigated based on push-out tests. Considering the effects of FTCs, a modified formula for calculating the shear capacity of headed stud connectors is proposed following GB 50017-2017. Results show that stud connectors' shear capacity and stiffness will deteriorate after FTCs. The two failure modes of stud shearing or concrete cracking will change with the aggravation of the FTCs effect.