Icelandic streams with mean annual temperatures of less than 5°C, which receive the cationic products of basaltic rock weathering, were found to host mats of iron-cycling microorganisms. We investigated two representative sites. Iron-oxidizing Gallionella and iron-reducing Geobacter species were present. The mats host a high bacterial diversity as determined by culture-independent methods. β-Proteobacteria, Actinobacteria, α-Proteobacteria, and Bacteroidetes were abundant microbial taxa. The mat contained a high number of phototroph sequences. The carbon compounds in the mat displayed broad G and D bands with Raman spectroscopy. This signature becomes incorporated into the weathered oxidized surface layer of the basaltic rocks and was observed on rocks that no longer host mats. The presence of iron-oxidizing taxa in the stream microbial mats, and the lack of them in previously studied volcanic rocks in Iceland that have intermittently been exposed to surface water flows, can be explained by the kinetic limitations to the extraction of reduced iron from rocks. This type of ecosystem illustrates key factors that control the distribution of chemolithotrophs in cold volcanic environments. The data show that one promising sample type for which the hypothesis of the existence of past life on Mars can be tested is the surface of volcanic rocks that, previously, were situated within channels carved by flowing water. Our results also show that the carbonaceous signatures of life, if life had occurred, could be found in or on these rocks. Key Words: Bioenergetics—Chemolithotrophic microorganisms—Iron-oxidizing bacteria—Iron-reducing bacteria—Volcanism. Astrobiology 11, 679–694.