The vast majority of the Earth's biological diversity is hidden in uncultured and yet uncharacterized microbial genomes. The construction of metagenomic libraries is a cultivation-independent molecular approach to assess this unexplored genetic reservoir. In the last few years, a high number of novel biocatalysts have been identified by function-based or sequence-based screening of metagenomic libraries. Here, we describe detailed protocols for the construction of metagenomic small-insert and large-insert libraries in plasmids and fosmids, respectively, from environmental DNA.