Graffiti can create detrimental aesthetic and environmental damage to city infrastructure and cultural heritage and requires improved removal methods. Incumbent laser, mechanical and chemical removal techniques are often not effective, are expensive or damage the substrate. Solvents are generally hazardous and not always effective because of the insolubility of the graffiti paint. This study proposes a simple strategy for safe and effective graffiti removal, using the bio-based, non-toxic and biodegradable solvent dihydrolevoglucosenone (Cyrene™). The results showed that the type of substrate influenced the cleaning performance; in benchmark studies a non-porous substrate was easy to clean, while porous ceramic showed the presence of residual paint and yellowing when the conventional polar aprotic solvents were used. Cyrene, however, showed good removability of graffiti paint from both glazed and porous substrates, with little paint remaining in the pores of ceramic tiles. The paint suffered a reversible change in colour and a selective solubility of its components when using N-methyl-2-pyrrolidone; no changes occurred when Cyrene was used. While N-methyl-2-pyrrolidone and N,N′-dimethylformamide were only effective when neat, a Cyrene–water mixture showed some cleaning results. The performance of Cyrene was validated with Hansen solubility parameters and represents a greener and more sustainable solvent for paint removal.