This study examines the microbial colonization of three fronts of an abandoned dolostone quarry (Redueña, Madrid, Spain) exposed to atmospheric conditions for different time periods since Roman times to the present. Through scanning electron microscopy in backscattered electron mode (SEM-BSE), endolithic colonization was predominantly detected in the most recently exposed front, while in the longer exposed quarry fronts, epilithic forms of growth were most often observed. These observations were confirmed by denaturing gradient gel electrophoresis (DGGE) analysis. Based on the distribution pattern of microbial colonization in the different quarry fronts, we then established a sequence of colonization events that took place over this long time frame. Bioalteration processes related to this sequential colonization were also identified. Characterizing these sequential processes can be useful for interpreting biodeterioration processes in historic dolostone monuments, especially those affecting constructions in the area of the Redueña stone quarry. In a second experimental stage, different biocide treatments were tested on this quarry rock to find the best way to avoid the microbial colonization effects identified. Through combined SEM-BSE/DGGE analysis, the efficacy of several biocides against the microorganisms inhabiting the dolostones was assessed after 4 and 16 months treatment. In general, all treatments were effective at reducing around 80% of the lichen cover, although effects on endolithic lithobiontic communities were dependent on how well the rock surface had been mechanically cleaned prior to treatment and gradually disappeared over time.