The Arctic is warming - fast. Microbes in the Arctic play pivotal roles in feedbacks that magnify the impacts of Arctic change. Understanding the genome evolution, diversity and dynamics of Arctic microbes can provide insights relevant for both fundamental microbiology and interdisciplinary Arctic science. Within this synthesis, we highlight four key areas where genomic insights to the microbial dimensions of Arctic change are urgently required: the changing Arctic Ocean, greenhouse gas release from the thawing permafrost, 'biological darkening' of glacial surfaces, and human activities within the Arctic. Furthermore, we identify four principal challenges that provide opportunities for timely innovation in Arctic microbial genomics. These range from insufficient genomic data to develop unifying concepts or model organisms for Arctic microbiology to challenges in gaining authentic insights to the structure and function of low-biomass microbiota and integration of data on the causes and consequences of microbial feedbacks across scales. We contend that our insights to date on the genomics of Arctic microbes are limited in these key areas, and we identify priorities and new ways of working to help ensure microbial genomics is in the vanguard of the scientific response to the Arctic crisis.