Ubiquitous bacteria from the genus Oleispira drive oil degradation in the largest environment on Earth, the cold and deep sea. Here we report the genome sequence of Oleispira antarctica and show that compared with Alcanivorax borkumensis--the paradigm of mesophilic hydrocarbonoclastic bacteria--O. antarctica has a larger genome that has witnessed massive gene-transfer events. We identify an array of alkane monooxygenases, osmoprotectants, siderophores and micronutrient-scavenging pathways. We also show that at low temperatures, the main protein-folding machine Cpn60 functions as a single heptameric barrel that uses larger proteins as substrates compared with the classical double-barrel structure observed at higher temperatures. With 11 protein crystal structures, we further report the largest set of structures from one psychrotolerant organism. The most common structural feature is an increased content of surface-exposed negatively charged residues compared to their mesophilic counterparts. Our findings are relevant in the context of microbial cold-adaptation mechanisms and the development of strategies for oil-spill mitigation in cold environments.