The permafrost soils of the high elevation McMurdo Dry Valleys are the most cold, desiccating and oligotrophic on Earth. Rhodococcus sp. JG3 is one of very few bacterial isolates from Antarctic Dry Valley permafrost, and displays subzero growth down to -5 degrees C. To understand how Rhodococcus sp. JG3 is able to survive extreme permafrost conditions and be metabolically active at subzero temperatures we sequenced its genome and compared it to the genomes of 14 mesophilic rhodococci. Rhodococcus sp. JG3 possessed a higher copy number of genes for general stress response, UV protection and protection from cold shock, osmotic stress and oxidative stress. We characterized genome wide molecular adaptations to cold, and identified genes that had amino acid compositions favourable for increased flexibility and functionality at low temperatures. Rhodococcus sp. JG3 possesses multiple complimentary strategies which may enable its survival in some of the harshest permafrost on Earth.