Anti-Graffiti Systems (AGS) are meant to make the cleaning process more efficient by inserting a layer between the paint and the substrate. This layer can have a low surface energy thus make it difficult for the paint to stick to the substrate or it may be easily removed together with the paint. This paper is presenting results from a study of how hydrophobicity and oleophobicity influence the cleaning efficiency of graffiti paints from concrete and natural stones. The results demonstrated that high hydrophobicity and high oleophobicity are not guaranteeing satisfying cleaning effects. The physical properties of a substrate in combination with the characteristics of the AGS layer decide about the cleaning effect.