This paper presents preliminary results in determining the optimum parameters for graffiti removal in a ornamental granite, Rosa Porrino, by means of Nd:YVO4 laser at the wavelength of 355 nm and different fluences. The spray-paints (black, blue, red and silver) tested in this work were chemically characterized by means of elemental analysis, XRF, SEM/EDX and FTIR. The assessment of cleaning and characterization of the stone substrate before and after irradiation was performed by means of optical microscopy, SEM-EDX, and confocal microscopy. The analysis of the irradiated samples showed in some cases, damage in the granite substrate associated to thermal effects. The severity and kind of damage, depends on the laser fluence delivered, the constituent mineral irradiated, and the color used to paint the stone. So, at the highest levels of fluence the laser beam is able to scratch the surface, being the depth of the grooves in the stone measured by confocal microscopy. Moreover, SEM images show the differential damage caused in mineral constituents of granite i.e., quartz, feldspars, and biotite, the latter providing to be the most affected mineral, reaching melting even at low levels of fluence. It was appreciated that the color of the spray-paint affects the results of cleaning, and observed differences could be attributed to different organic constituents in the paints or the presence of metallic particles in its composition, as occurs with silver paint.