Self-healing polymers hold great promise for the future, enhancing in particular the longevity of polymeric materials. We describe a self-healing covalent polymer, presenting an extensive array of hydrogen-bonding sites based on the combination of urea, urethane, and bis-acyl-hydrazine units. Solvent-cast thin-films prepared by polycondensation of a commercially available dihydrazide and a diisocyanate prepolymer exhibited excellent room temperature autonomous healing with almost full recovery of mechanical properties when two parts of a cut film were overlapped and gently pressed together. This autonomous healing upon damage may be attributed to the supramolecular dynamics of multiple lateral inter-chain hydrogen-bonding interactions between the polymer chains. The solid-state structure of a model compound incorporating the same structural backbone corroborates the existence of an extensive two-dimensional supramolecular hydrogen-bonding network.