Environmental DNA is an extremely rich source of genes encoding enzymes with novel biocatalytic activities. To tap this source, function-based and sequence-based strategies have been established to isolate, clone, and express these novel metagenome-derived genes. Sequence-based strategies, which rely on PCR with consensus primers and genome walking, represent an efficient and inexpensive alternative to activity-based screening of recombinant strains harbouring fragments of environmental DNA. This review covers the diverse array of genome-walking techniques, which were originally developed for genomic DNA and currently are also used for PCR-based recovery of entire genes from the metagenome. These sequence-based gene mining methods appear to offer a powerful tool for retrieving from the metagenome novel genes encoding biocatalysts with potential applications in biotechnology.