Carbon dioxide removal options have been identified as key to achieving the climate change target laid out in the 2015 Paris Agreement. Bioenergy with carbon capture and storage (BECCS) is particularly attractive because it is capable of providing negative emissions and a reliable energy source. We here explore the complexity of the infrastructures involved in realizing a large-scale system and the sequestration potential of bioenergy in Europe. Starting from a minimum cost scenario, we develop cost-optimal solutions that minimize the environmental impact of the overall BECCS supply chain according to the life cycle impact assessment methodology. Our analysis is based on cooperation among the 28 countries of the European Union (as of 2018) to achieve a global carbon removal target. Given regional biomass and marginal land availability inputs and a carbon removal target of 0.61 GtCO2/year, the minimum-cost scenario provides negative emissions, with an overall cost of 140 Eur/MWh of bioelectricity generated or 117 Eur/tCO2 removed, without considering revenues from selling the electricity produced. On the other hand, minimizing environmental impacts increased costs by 45% relative to the first scenario, but further improved the environmental performance by 23%.