Despite >130 years of microbial cultivation studies, many microorganisms remain resistant to traditional cultivation approaches, including numerous candidate phyla of bacteria and archaea. Unraveling the mysteries of these candidate phyla is a grand challenge in microbiology and is especially important in habitats where they are abundant, including some extreme environments and low-energy ecosystems. Over the past decade, parallel advances in DNA amplification, DNA sequencing and computing have enabled rapid progress on this problem, particularly through metagenomics and single-cell genomics. Although each approach suffers limitations, metagenomics and single-cell genomics are particularly powerful when combined synergistically. Studies focused on extreme environments have revealed the first substantial genomic information for several candidate phyla, encompassing putative acidophiles (Parvarchaeota), halophiles (Nanohaloarchaeota), thermophiles (Acetothermia, Aigarchaeota, Atribacteria, Calescamantes, Korarchaeota, and Fervidibacteria), and piezophiles (Gracilibacteria). These data have enabled insights into the biology of these organisms, including catabolic and anabolic potential, molecular adaptations to life in extreme environments, unique genomic features such as stop codon reassignments, and predictions about cell ultrastructure. In addition, the rapid expansion of genomic coverage enabled by these studies continues to yield insights into the early diversification of microbial lineages and the relationships within and between the phyla of Bacteria and Archaea. In the next 5 years, the genomic foliage within the tree of life will continue to grow and the study of yet-uncultivated candidate phyla will firmly transition into the post-genomic era.