Many petroleum-polluted areas are considered as extreme environments because of co-occurrence of low and high temperatures, high salt, and acidic and anaerobic conditions. Alkanes, which are major constituents of crude oils, can be degraded under extreme conditions, both aerobically and anaerobically by bacteria and archaea of different phyla. Alkane degraders possess exclusive metabolic pathways and survival strategies, which involve the use of protein and RNA chaperones, compatible solutes, biosurfactants, and exopolysaccharide production for self-protection during harsh environmental conditions such as oxidative and osmotic stress, and ionic nutrient-shortage. Recent findings suggest that the thermophilic sulfate-reducing archaeon Archaeoglobus fulgidus uses a novel alkylsuccinate synthase for long-chain alkane degradation, and the thermophilic Candidatus Syntrophoarchaeum butanivorans anaerobically oxidizes butane via alkyl-coenzyme M formation. In addition, gene expression data suggest that extremophiles produce energy via the glyoxylate shunt and the Pta-AckA pathway when grown on a diverse range of alkanes under stress conditions. Alkane degraders possess biotechnological potential for bioremediation because of their unusual characteristics. This review will provide genomic and molecular insights on alkane degraders under extreme conditions.