The aim of this research was to determine the accelerating effects of microorganisms on the biodeterioration of stone under air pollution and continental-cold climatic region in Erzurum, Turkey. Studies have been carried out on specimens of the Rustempasa Bazaar, the Lalapasa Mosque, the Erzurum Castle Mosque, the Double Minarets-Madrasah, the Great Mosque and the Haji Mehmet Fountain aged from 441 to 823 years old. The results showed that vegetative and reproductive (generative) forms of the microorganisms could develop during the winter months when the night time average temperature was even -25 degrees C. Also the reproductive forms had developed and the whole stone surface was covered with a biofilm caused by the microorganisms. Silicon, aluminum, calcium, potassium, titanium, magnesium, zinc, sulfur, iron, sodium, and niobium were found in the stones of the historical buildings with varying amounts through the SEM-EDS analysis. Some of these elements could be used as an energy resource for the microorganisms together with the air pollutants such as sulfur dioxide, nitrogen oxides and particles on the stone surfaces. Of 21 isolates, 15 species from 6 bacterium genera and 5 species from 5 fungi genera plus 1 fungi genera were identified on the deteriorated stone surfaces even during the coldest months by microbial identification system (MIS) and these findings were tested by SEM investigations.