Self-healing polymers crosslinked by solely reversible bonds are intrinsically weaker than common covalently crosslinked networks. Introducing covalent crosslinks into a reversible network would improve mechanical strength. It is challenging, however, to apply this concept to "dry" elastomers, largely because reversible crosslinks such as hydrogen bonds are often polar motifs, whereas covalent crosslinks are nonpolar motifs. These two types of bonds are intrinsically immiscible without cosolvents. Here, we design and fabricate a hybrid polymer network by crosslinking randomly branched polymers carrying motifs that can form both reversible hydrogen bonds and permanent covalent crosslinks. The randomly branched polymer links such two types of bonds and forces them to mix on the molecular level without cosolvents. This enables a hybrid "dry" elastomer that is very tough with fracture energy 13500 Jm comparable to that of natural rubber. Moreover, the elastomer can self-heal at room temperature with a recovered tensile strength 4 MPa, which is 30% of its original value, yet comparable to the pristine strength of existing self-healing polymers. The concept of forcing covalent and reversible bonds to mix at molecular scale to create a homogenous network is quite general and should enable development of tough, self-healing polymers of practical usage.