The exploration of petroleum source, production, and transportation in cold environments is increasing tremendously. These activities have made cold regions of the earth vulnerable to oil-contamination. In cold environments, oil-based contaminants persist longer than they do in temperate region because of the low bioavailability of hydrocarbons and the harsh climatic conditions. Oil-based contaminants must be removed to maintain biodiversity and ecological balance. During the last fifteen years, several bioremediation strategies have been employed in cold regions. One effective bioremediation strategy is the introduction of potent cold adaptive microorganism combining with amendment of physio-chemical parameters into the contaminated sites. However, this approach is still in its infancy compared to the use of mesophilic microorganisms. The current bioremediation practices employed in cold regions suffer with several problems such as lack of potent oil-degraders, poor bioavailability of hydrocarbons, and low temperature, oxygen, and nutrient level. Understanding on these aspects is essential for successful bioremediation in cold environments. This review discusses the current bioremediation strategies, the limiting factors governing bioremediation, and the mechanism of biodegradation in cold regions. Furthermore, culture-independent techniques for assessing potent microbes, laboratory cultivation techniques for isolating psychrophilic oil-degraders and conceptual strategies of bioaugmentation are presented.