Only a small minority of microorganisms from an environmental sample can be cultured in the laboratory leaving the enormous bioprospecting potential of the uncultured diversity unexplored. This resource can be accessed by improved cultivation methods in which the natural environment is brought into the laboratory or through metagenomic approaches where culture-independent DNA sequence information can be combined with functional screening. The coupling of these two approaches circumvents the need for pure, cultured isolates and can be used to generate targeted information on communities enriched for specific activities or properties. Bioprospecting in extreme environments is often associated with additional challenges such as low biomass, slow cell growth, complex sample matrices, restricted access, and problematic in situ analyses. In addition, the choice of vector system and expression host may be limited as few hosts are available for expression of genes with extremophilic properties. This review summarizes the methods developed for improved cultivation as well as the metagenomic approaches for bioprospecting with focus on the challenges faced by bioprospecting in cold environments.