It is challenging to fabricate mechanically super-strong polymer composites with excellent healing capacity because of the significantly limited mobility of polymer chains. The fabrication of mechanically super-strong polymer composites with excellent healing capacity by complexing polyacrylic acid (PAA) with polyvinylpyrrolidone (PVPON) in aqueous solution followed by molding into desired shapes is presented. The coiled PVPON can complex with PAA in water via hydrogen-bonding interactions to produce transparent PAA-PVPON composites homogenously dispersed with nanoparticles of PAA-PVPON complexes. As healable materials, the PAA-PVPON composite materials with a glass transition temperature of ≈107.9 °C exhibit a super-high mechanical strength, with a tensile strength of ≈81 MPa and a Young's modulus of ≈4.5 GPa. The PAA-PVPON composites are stable in water because of the hydrophobic interactions among pyrrolidone groups. The super-high mechanical strength of the PAA-PVPON composite materials originates from the highly dense hydrogen bonds between PAA and PVPON and the reinforcement of in situ formed PAA-PVPON nanoparticles. The reversibility of the relatively weak but dense hydrogen bonds enables convenient healing of the mechanically strong PAA-PVPON composite materials from physical damage to restore their original mechanical strength.