Emission budgets are defined as the cumulative amount of anthropogenic CO₂ emission compatible with a global temperature-change target. The simplicity of the concept has made it attractive to policy-makers, yet it relies on a linear approximation of the global carbon-climate system's response to anthropogenic CO2 emissions. Here we investigate how emission budgets are impacted by the inclusion of CO₂ and CH₄ emissions caused by permafrost thaw, a non-linear and tipping process of the Earth system. We use the compact Earth system model OSCAR v2.2.1, in which parameterizations of permafrost thaw, soil organic matter decomposition and CO₂ and CH₄ emission were introduced based on four complex land surface models that specifically represent high-latitude processes. We found that permafrost carbon release makes emission budgets path dependent (that is, budgets also depend on the pathway followed to reach the target). The median remaining budget for the 2 °C target reduces by 8% (1-25%) if the target is avoided and net negative emissions prove feasible, by 13% (2-34%) if they do not prove feasible, by 16% (3-44%) if the target is overshot by 0.5 °C and by 25% (5-63%) if it is overshot by 1 °C. (Uncertainties are the minimum-to-maximum range across the permafrost models and scenarios.) For the 1.5 °C target, reductions in the median remaining budget range from ~10% to more than 100%. We conclude that the world is closer to exceeding the budget for the long-term target of the Paris Climate Agreement than previously thought.