The preparation of new responsive hydrogels is crucial for the development of soft materials for various applications, including additive manufacturing and biomedical implants. Here, we report the discovery of a new mechanism for forming physical hydrogels by the arrested phase separation of a subclass of responsively hydrophobic elastin-like polypeptides (ELPs). When moderately concentrated solutions of ELPs with the pentapeptide repeat (XPAVG)(n) (where X is either 20% or 60% valine with the remainder isoleucine) are warmed above their inverse transition temperature, phase separation becomes arrested, and hydrogels can be formed with shear moduli on the order of 0.1-1 MPa at 20 wt % in water. The longest stress relaxation times are well beyond 10(3) s. This result is surprising because ELPs are classically known for thermoresponsive coacervation that leads to macrophase separation, and solids are typically formed in the bulk or by supplemental cross-linking strategies. This new mechanism can form gels with remarkable mechanical behavior based on simple macromolecules that can be easily engineered. Small angle scattering experiments indicate that phase separation arrests to form a network of nanoscale domains, exhibiting rheological and structural features consistent with an arrested spinodal decomposition mechanism. Gel nanostructure can be modeled as a disordered bicontinuous network with interdomain, intradomain, and curvature length scales that can be controlled by sequence design and assembly conditions. These studies introduce a new class of reversible, responsive materials based on a classic artificial biopolymer that is a versatile platform to address critical challenges in industrial and medical applications.