The land-use sector can contribute to climate change mitigation not only by reducing greenhouse gas (GHG) emissions, but also by increasing carbon uptake from the atmosphere and thereby creating negative CO2 emissions. In this paper, we investigate two land-based climate change mitigation strategies for carbon removal: (1) afforestation and (2) bioenergy in combination with carbon capture and storage technology (bioenergy CCS). In our approach, a global tax on GHG emissions aimed at ambitious climate change mitigation incentivizes land-based mitigation by penalizing positive and rewarding negative CO2 emissions from the land-use system. We analyze afforestation and bioenergy CCS as standalone and combined mitigation strategies. We find that afforestation is a cost-efficient strategy for carbon removal at relatively low carbon prices, while bioenergy CCS becomes competitive only at higher prices. According to our results, cumulative carbon removal due to afforestation and bioenergy CCS is similar at the end of 21st century (600–700 GtCO2), while land-demand for afforestation is much higher compared to bioenergy CCS. In the combined setting, we identify competition for land, but the impact on the mitigation potential (1000 GtCO2) is partially alleviated by productivity increases in the agricultural sector. Moreover, our results indicate that early-century afforestation presumably will not negatively impact carbon removal due to bioenergy CCS in the second half of the 21st century. A sensitivity analysis shows that land-based mitigation is very sensitive to different levels of GHG taxes. Besides that, the mitigation potential of bioenergy CCS highly depends on the development of future bioenergy yields and the availability of geological carbon storage, while for afforestation projects the length of the crediting period is crucial.