Bacteria inhabiting crystalline rocks from two terrestrial Icelandic volcanic lava flows of similar age and from the same geographical region, but differing in porosity and mineralogy, were characterized. Microarray (PhyloChip) and clone library analysis of 16S rRNA genes revealed the presence of a diverse assembly of bacteria in each lava flow. Both methods suggested a more diverse community at the Dómadalshraun site (rhyolitic / andesitic lava flow) than that present at the Hnausahraun site (basaltic lava flow). Proteobacteria dominated the clone library at the Dómadalshraun site, while Acidobacteria was the most abundant phylum in the Hnausahraun site. Although analysis of similarities of denaturing gradient gel electrophoresis profiles suggested a strong correlation of community structure with mineralogy, rock porosity may also play an important role in shaping the bacterial community in crystalline volcanic rocks. Clone sequences were most similar to uncultured microorganisms, mainly from soil environments. Of these, Antarctic soils and temperate rhizosphere soils were prominent, as were clones retrieved from Hawaiian and Andean volcanic soils. The novel diversity of these Icelandic microbial communities was supported by the finding that up to 46% of clones displayed <85% sequence identities to sequences currently deposited in the RDP database.