Natural climate solutions (NCS) in the Arctic hold the potential to be implemented at a scale able to substantially affect the global climate. The strong feedbacks between carbon-rich permafrost, climate and herbivory suggest an NCS consisting of reverting the current wet/moist moss and shrub-dominated tundra and the sparse forest-tundra ecotone to grassland through a guild of large herbivores. Grassland-dominated systems might delay permafrost thaw and reduce carbon emissions-especially in Yedoma regions, while increasing carbon capture through increased productivity and grass and forb deep root systems. Here we review the environmental context of megafaunal ecological engineering in the Arctic; explore the mechanisms through which it can help mitigate climate change; and estimate its potential-based on bison and horse, with the aim of evaluating the feasibility of generating an ecosystem shift that is economically viable in terms of carbon benefits and of sufficient scale to play a significant role in global climate change mitigation. Assuming a megafaunal-driven ecosystem shift we find support for a megafauna-based arctic NCS yielding substantial income in carbon markets. However, scaling up such projects to have a significant effect on the global climate is challenging given the large number of animals required over a short period of time. A first-cut business plan is presented based on practical information-costs and infrastructure-from Pleistocene Park (northeastern Yakutia, Russia). A 10 yr experimental phase incorporating three separate introductions of herds of approximately 1000 individuals each is costed at US$114 million, with potential returns of approximately 0.3-0.4% yr towards the end of the period, and greater than 1% yr after it. Institutional friction and the potential role of new technologies in the reintroductions are discussed. This article is part of the theme issue 'Climate change and ecosystems: threats, opportunities and solutions'.