Three samples taken from two paintings partly burned by fire are investigated for cleaning with lasers. The paintings belong to the collection of the National Gallery of Athens and were made by the great Greek artist Konstantinos Parthenis. To remove the damaged surface and achieve an acceptable restoration result, the optimum combination of fluence and wavelength are sought. Seven different wavelengths with a set of fluences where used, i.e., the five harmonics of a Nd:YAG laser (1064, 532, 355, 266, and 213 nm), a TEA 10.6 μm CO2 and a free running laser Er:YAG 2.94 μm. Characterization was performed prior and after the cleaning process by optical and electron microscopy and analysis (SEM/BSE EDS), as well as X-Ray Diffraction (XRD). The results of this work indicate that the wavelength in the visible spectrum (532 nm) with fluences between 0.1–0.4J/cm2 show the optimum cleaning. The optical microscopy observation shows that with these laser parameters the burnt layer was preferentially removed, exposing the original colors that Parthenis had used in these paintings. Electron microscopy imaging and chemical analysis revealed that the original texture and materials of these samples are preserved after irradiation. Since the damage varies along the surface of the painting, more experiments should be performed in order to find and optimize the full cleaning and characterization process for the homogeneous cleaning of the whole surface of the painting.