Viable bacteria were found in permafrost core samples from the Kolyma-Indigirka lowland of northeast Siberia. The samples were obtained at different depths; the deepest was about 3 million years old. The average temperature of the permafrost is −10°C. Twenty-nine bacterial isolates were characterized by 16S rDNA sequencing and phylogenetic analysis, cell morphology, Gram staining, endospore formation, and growth at 30°C. The majority of the bacterial isolates were rod shaped and grew well at 30°C; but two of them did not grow at or above 28°C, and had optimum growth temperatures around 20°C. Thirty percent of the isolates could form endospores. Phylogenetic analysis revealed that the isolates fell into four categories: high-GC Gram-positive bacteria, β-proteobacteria, γ-proteobacteria, and low-GC Gram-positive bacteria. Most high-GC Gram-positive bacteria and β-proteobacteria, and all γ-proteobacteria, came from samples with an estimated age of 1.8–3.0 million years (Olyor suite). Most low-GC Gram-positive bacteria came from samples with an estimated age of 5,000–8,000 years (Alas suite).