Recycling of waste rubber into concrete is one of the most efficacious and environmentally-friendly methods to solve the so-called black pollution. However, the incorporation of waste rubber particles reduces the mechanical properties of concrete, resulting from the low stiffness of the rubber particles as well as the insufficient adhesion energy between waste rubber and hardened cement paste. To solve the latter issue, an innovative surface treatment method for hydrophilicity improvement of waste rubber using polyvinyl alcohol (PVA) is proposed in this paper. The interfacial strengthening mechanism of waste rubber/cement paste using PVA is systematically studied from the aspects of macro-scopic mechanical properties, micro-structure characteristics and molecular-scale modifications. The addition of 0.1% PVA solution can significantly enhance the compressive and flexural strength of rubber-cement composites by 7–14% and 20–38% at the age of 28 days, respectively. SEM observation and EDS results verify the bridging effect of PVA at the waste rubber/cement paste interface, which eliminates the gap caused by the hydrophobicity of rubber. The molecular dynamics simulation shows that the interfacial adhesion energy between rubber hydrocarbon (RH) and PVA is 52% higher than that between RH and calcium-silicate-hydrate (C–S–H), resulting in the accumulation of PVA molecules on rubber surface by van der Waals force and electrostatic interaction. The RH/PVA/C–S–H model has better mechanical properties than the RH/C–S–H model, verifying the bridging role of PVA at the molecular scale.