Five different methods for cleaning the limestone façades on what was originally the Workers Hospital in Madrid are analyzed in this paper. Due to the pollution in the surrounding air, just 20 years after a prior cleaning operation, sulfate crusts had developed on the entire stone surface of the building. The gypsum mortar used in the original masonry constituted an additional source of sulfur. Limestone is a traditional building material in Madrid and its surroundings. The petrography, mineralogy and petrophysical properties of the biomicrite, pelmicrite and biopelmicrite varieties of limestone identified in the hospital walls were determined. Analysis of a black layer on the stone surface showed that it consisted primarily of sulfate crusts. The cleaning methods tested were alkaline gels (sodium hydroxide and potassium hydroxide), pressurized hot water, glass bead blasting and latex peeling. The criteria for assessing the effectiveness and potential risks of the various cleaning systems included changes in the chromatic parameters of the stone, the formation of alteration products (i.e. salts) and modification of the stone surface. The stones cleaned with the three most effective methods, together with a rain-washed stone as a reference, were washed with water to generate an artificial runoff. The collected drain water was analyzed to determine the presence of any by-products from the cleaning process. The method found to be most effective and which caused the least alteration to the stone surface was glass bead blasting, particularly after adjustment of the bead size and pressure conditions used for the test.