In one of the central scenarios for meeting an European Union-wide net zero greenhouse gas (GHG) emissions target by 2050, the emissions cap in the European Union Emissions Trading System (EU ETS) becomes net negative. Despite this ambition, no mechanism allows for the inclusion of CO2 removal credits (CRCs) in the EU ETS to date. Amending the EU ETS legislation is required to create enabling conditions for a net negative cap. Here, we conceptually discuss various economic, legal, and political challenges surrounding the integration of CRCs into the EU ETS. To analyze cap-and-trade systems encompassing negative emissions, we introduce the effective (elastic) cap resulting from the integration of CRCs in addition to the regulatory (inelastic) cap, the latter now being binding for the net emissions only. Given current cost estimates for BECCS and DACCS, minimum quantities for the use of removals, as opposed to ceilings as currently discussed, would be required to promote the near-term integration of such technologies. Instead of direct interaction between the companies involved in emissions trading and the providers of CRCs, the regulatory authority could also transitionally act as an intermediary by buying CRCs and supplying them in turn conditional upon observed allowances prices, for example, by supporting a (soft) price collar. Contrary to a price collar without dedicated support from CRCs, in this case (net) compliance with the overall cap is maintained. EU legislation already provides safeguards for physical carbon leakage concerning CCS, making Bioenergy with Carbon Capture and Storage (BECCS) and Direct Air Capture and Storage prioritized for inclusion in the EU ETS. Furthermore, a special opportunity might apply for the inclusion of BECCS installations. Repealing the provision that installations exclusively using biomass are not covered by the ETS Directive, combined with freely allocated allowances to these installations, would allow operators of biomass installations to sell allowances made available through the use of BECCS. Achieving GHG neutrality in the EU by 2050 requires designing suitable incentive systems for CO2 removal, which includes the option to open up EU emissions trading to CRCs.