Abstract: Wall paintings make up an important section of cultural heritage. They resemble time portals that can be used to travel back into the past and witness the life of our ancestors. In these paintings, the ancient artists depicted the different aspects of their life, such as cooking, baking, farming, manufacturing, as well as thoughts and beliefs. Unfortunately, wall paintings are susceptible to degradation over time in the form of the accumulations of dirt and deposits on the painted surfaces and loss of adhesion of the paint layers at the surface. Therefore, the removal of these deposits is one of the primary duties of conservator-restorers. Such operations are intended to restore the painted surface to a condition close enough to its original state. Since cleaning artworks may cause undesirable physicochemical alterations and is nonreversible, the proper cleaning procedure should be adopted. In this regard, numerous gels have been developed and exploited for the cleaning of various artwork surfaces. Lately, polyvinyl alcohol-borax (PVA-B) and agarose (AG) hydrogels have been widely employed as cleaning materials by conservator-restorers. However, both hydrogels have shown limitations in specific cleaning practices. In this work, we investigated a new double network hydrogel based on blending PVA-B and agarose to avoid the limitations posed by the constituting hydrogels. For this reason, a detailed characterization of the PVA–B/AG double network hydrogel was performed, including chemical structure, liquid phase retention, mechanical strength, rheological behavior, and self-healing behavior of various PVA-B/AG hydrogels. These new hydrogels revealed better properties than PVA-B and agarose hydrogels and obviated their limitations. A laboratory experiment on the removal of deteriorated Paraloid® B72 proved that the PVA-B/AG hydrogel loaded 10%/10% MEK/1-PeOH was able to remove these layers efficiently. Therefore, the hydrogel was tested on a wall painting from the Temple of Seti I in Abydos – Egypt. It removed the glossy/darkened consolidant from the wall painting and restored the original matt appearance of the painted surface. In another application on the painted ceiling of the same temple, the hydrogel was tested for removing thick soot layers. The hydrogel formulation (loaded with 5% ammonia, 0.3% ammonium carbonate, and 0.3% EDTA) removed these layers with no noticeable damage to the paint layers. In a wide-scale application of the hydrogel (loaded with 10% propylene carbonate), it removed a highly deteriorated varnish layer from a 19-c wall painting. All the traditional cleaning methods employed caused damage to the paint layers, proving that gel cleaning can be a safer cleaning alternative in some cases.