Benthic microbial mats dominated by Cyanobacteria are important features of polar lakes. Although culture-independent studies have provided important insights into the diversity of polar Cyanobacteria, only a handful of genomes have been sequenced to date. Here, we applied a genome-resolved metagenomics approach to data obtained from Arctic, sub-Antarctic and Antarctic microbial mats. We recovered 37 metagenome-assembled genomes (MAGs) of Cyanobacteria representing 17 distinct species, most of which are only distantly related to genomes that have been sequenced so far. These include (i) lineages that are common in polar microbial mats such as the filamentous taxa Pseudanabaena , Leptolyngbya , Microcoleus / Tychonema and Phormidium; (ii) the less common taxa Crinalium and Chamaesiphon ; (iii) an enigmatic Chroococcales lineage only distantly related to Microcystis ; and (iv) an early branching lineage in the order Gloeobacterales that is distributed across the cold biosphere, for which we propose the name Candidatus Sivonenia alaskensis. Our results show that genome-resolved metagenomics is a powerful tool for expanding our understanding of the diversity of Cyanobacteria, especially in understudied remote and extreme environments.