Elastic physical gels are highly desirable because they can be conveniently prepared and readily shaped. Unfortunately, many elastic physical gels prepared in water require in situ free-radical polymerization during the gel formation stage. In contrast, complex coacervate gels are physical gels that can be prepared by simply mixing two pre-formed oppositely-charged polyelectrolytes. However, as far as we are aware, highly elastic complex coacervate gels have not yet been reported. Herein, we combine polyanionic microgel particles with a well-known commercially-available cationic polyelectrolyte to prepare polymer/microgel complex coacervate (PMCC) physical gels. This new family of gels requires annealing at only 37 °C and behaves like a covalent gel but does not form covalent bonds. Thermal reconfiguration of the dynamic ionic bonds transforms the shapeable pre-gel into a highly elastic gel that is super-stretchable, adhesive, self-healing, highly swellable and can be further toughened using Ca2+ as an ionic crosslinker. Our PMCC gels have excellent potential for applications as engineering gels and structural biomaterials, as well as for wound healing and water purification.