Considering that conventional shear connectors cannot be applied to steel-ultra-high performance concrete (UHPC) composite deck systems as the UHPC layer is too thin, a novel shear connector consisting of specified designed pre-embedded sleeve and high-strength bolt was proposed, which can realize the rapid assembly and disassembly of prefabricated UHPC and steel member. Push-out tests on six groups of specimens were conducted, including five sets of high-strength bolt connectors and a set of negative Poisson’s ratio bolt connector. The failure pattern and load-slip curve characteristics of the novel shear connectors were analyzed. The effects of different parameters (diameter, aspect ratio, and type) of bolts on the mechanical properties (ultimate slip and shear stiffness) of the novel shear connector were discussed. Results show that the failure mode of the novel shear connectors was the shear-off failure of the bolt shank, and there was no apparent local collapse of UHPC under the pre-embedded sleeves. The shear capacity and the relative slip of the high-strength bolt connector increased with the increase in the diameter of the high-strength bolt. The shear capacity of the novel high-strength bolt connector was approximately 55.8% of the tensile strength of the bolt. Thus, bolt connectors with larger diameters are recommended in steel-UHPC composite structures to effectively reduce the number of shear connectors. The shear capacity and shear stiffness of the negative Poisson’s ratio bolt connector were significantly smaller, but the ultimate slip was significantly increased, showing good ductility. Therefore, it is suggested to apply negative Poisson’s ratio bolt to the negative moment section of steel-UHPC composite structure, so as to avoid cracking in the negative moment section.