In the last few years, the microbial colonisation of mural paintings in ancient monuments has been attracting the attention of microbiologists and conservators. The genus Rubrobacter is commonly found in biodeteriorated monuments, where it has been reported to cause rosy discolouration. However, to date, only three species of this genus have been isolated, all from thermophilic environments. In this paper, we studied three monuments: the Servilia and Postumio tombs in the Roman Necropolis of Carmona (Spain), and Vilar de Frades church (Portugal), in search of Rubrobacter strains. In all cases, biodeterioration and the formation of efflorescences were observed, and five Rubrobacter strains were isolated. These isolates showed different physiology and migration in denaturing gradient gel electrophoresis, suggesting they might represent new species within this genus. The isolates reproduced some biodeterioration processes in the laboratory and revealed their biomediation in crystal formation.