High-latitude soils store vast amounts of perennially frozen and therefore inert organic matter. With rising global temperatures and consequent permafrost degradation, a part of this carbon stock will become available for microbial decay and eventual release to the atmosphere. We have developed a simplified, two-dimensional multi-pool model to estimate the strength and timing of future carbon dioxide (CO2) and methane (CH4) fluxes from newly thawed permafrost carbon (i.e. carbon thawed when temperatures rise above pre-industrial levels). We have especially simulated carbon release from deep deposits in Yedoma regions by describing abrupt thaw under newly formed thermokarst lakes. The computational efficiency of our model allowed us to run large, multi-centennial ensembles under various scenarios of future warming to express uncertainty inherent to simulations of the permafrost carbon feedback. Under moderate warming of the representative concentration pathway (RCP) 2.6 scenario, cumulated CO2 fluxes from newly thawed permafrost carbon amount to 20 to 58 petagrams of carbon (Pg-C) (68% range) by the year 2100 and reach 40 to 98 Pg-C in 2300. The much larger permafrost degradation under strong warming (RCP8.5) results in cumulated CO2 release of 42 to 141 Pg-C and 157 to 313 Pg-C (68% ranges) in the years 2100 and 2300, respectively. Our estimates only consider fluxes from newly thawed permafrost, not from soils already part of the seasonally thawed active layer under pre-industrial climate. Our simulated CH4 fluxes contribute a few percent to total permafrost carbon release yet they can cause up to 40% of total permafrost-affected radiative forcing in the 21st century (upper 68% range). We infer largest CH4 emission rates of about 50 Tg-CH4 per year around the middle of the 21st century when simulated thermokarst lake extent is at its maximum and when abrupt thaw under thermokarst lakes is taken into account. CH4 release from newly thawed carbon in wetland-affected deposits is only discernible in the 22nd and 23rd century because of the absence of abrupt thaw processes. We further show that release from organic matter stored in deep deposits of Yedoma regions crucially affects our simulated circumpolar CH4 fluxes. The additional warming through the release from newly thawed permafrost carbon proved only slightly dependent on the pathway of anthropogenic emission and amounts to about 0.03–0.14 °C (68% ranges) by end of the century. The warming increased further in the 22nd and 23rd century and was most pronounced under the RCP6.0 scenario, adding 0.16 to 0.39 °C (68% range) to simulated global mean surface air temperatures in the year 2300.