The microbial composition of ancient permafrost sediments from the Kolyma lowland of Northeast Eurasia was examined through culture and culture-independent approaches. These sediments have been continuously frozen for 5,000 to 2–3 million years. A total of 265 Bacteria 16S rRNA gene sequences were amplified from the permafrost total-community genomic DNA and screened by amplified ribosomal 16S rRNA restriction analysis. Members of three major lineages were found: gamma-Proteobacteria (mostly Xanthomonadaceae), Actinobacteria, and Firmicutes. We also determined partial 16S rRNA gene sequences of 49 isolates from a collection of 462 aerobes isolated from these sediments. The bacteria included Actinomycetales (Arthrobacter and Microbacteriaceae); followed by the Firmicutes (Exiguobacterium and Planomicrobium); the Bacteroidetes (Flavobacterium); the gamma-Proteobacteria (Psychrobacter); and the alpha-Proteobacteria (Sphingomonas). Both culture and culture-independent approaches showed the presence of high and low G+C Gram-positive bacteria and gamma-Proteobacteria. Some of the 16S rRNA gene sequences of environmental clones matched those of Arthrobacter isolates. Two-thirds of the isolates grew at –2.5°C, indicating that they are psychroactive, and all are closely related to phylogenetic groups with strains from other cold environments, mostly commonly from Antarctica. The culturable and non-culturable microorganisms found in the terrestrial permafrost provide a prototype for possible life on the cryogenic planets of the Solar System.