Since it has been reported that microorganisms can affect painting pigments, Paleolithic painting microbiology deserves attention. The present study is the first report on the bacterial colonization of the valuable Paleolithic paintings in the famous Altamira cave (Spain). One sample taken from a painting area in the Polychromes Hall was analyzed culture-independently. This was the first time microbiologists were allowed to take sample material directly from Altamira paintings. Identification methods included PCR amplification of 16S rRNA genes (16S rDNA) and community fingerprinting by denaturing gradient gel electrophoresis (DGGE). The applied approach gave insight into a great bacterial taxonomic diversity, and allowed the detection of unexpected and unknown bacteria with potential effects on the conservation of the painting. Regarding the number of 29 visible DGGE bands in the community fingerprint, the numbers of analyzed clones described about 72% of the phylogenetic diversity present in the sample. Thirty-eight percent of the sequences analyzed were phylogenetically most closely related to cultivated bacteria, while the majority (62%) were most closely related to environmental 16S rDNA clones. Bacteria identified in Altamira were related with sequence similarities between 84.8 and 99.4% to members of the cosmopolitan Proteobacteria (52.3%), to members of the Acidobacterium division (23.8%), Cytophaga/Flexibacter/Bacteroides phylum (9.5%), green non-sulfur bacteria (4.8%), Planctomycetales (4.8%) and Actinobacteria (4.8%). The high number of clones most closely related to environmental 16S rDNA clones showed the broad spectrum of unknown and yet to be cultivated bacteria in Altamira cave.