Microorganisms have been considered agents causing biodeterioration of works of art. Nowadays they are however starting to be used for cleaning remains of organic compounds and salt crusts that are difficult to eliminate by traditional restoration methods. This work develops the use of Pseudomonas stutzeri for biocleaning mural paintings for the purpose of eliminating remains of organic materials from old restorations or insoluble saline efflorescence. To this end different strains of Pseudomonas stutzeri are used from type collections and different supports facilitating their direct applications on real work. The methods obtained in the preliminary tests are experimentally applied on the mural paintings of Santos Juanes Church in Valencia.