Graffiti vandalism represents an aesthetic and structural phenomenon of degradation both for buildings and cultural heritage: the most used sprays and markers can permeate the stone materials exposing them to degradation. Hence, great attention is being currently devoted to new non-invasive chemical approaches to face this urgent problem. This work is aimed at deeply examining the effects of some of the most sustainable chemical protective methods on the physical properties of natural building materials (e.g., tuff and limestone) by testing two commercial anti-graffiti products. It was found that the nanotechnological product Ector (E) was more effective than Nord Resine (NR) in anti-graffiti applications even if its permanent character hinders its application to the cultural heritage. Conversely, the less performant NR could be used in this field due to its sacrificial behavior, according to the guidelines of the Italian Ministry of Cultural Heritage and Activities and Tourism. The findings highlight the importance of developing new sustainable methods for the preservation of cultural and building materials from vandal graffiti, which should combine the high hydrophobia, the ecological characteristics, and the effectiveness of E, with the sacrificial properties of NR.