This paper investigates the energy efficiency, CO2 mitigation potential and CO2 mitigation cost of biomass-based combined heat and power production (CHP) with a CO2 capture option in Kraft pulp and paper mills. CHP systems based on black liquor and biomass gasifier with combined cycle technology and biomass boiler with steam turbine technology are considered. The study shows that steep CO2 reductions can be achieved through CO2 capture and storage regardless of CHP technology used although alternatives based on black liquor and biomass gasification provide the most efficient systems from a resource and energy point of view. Moreover, using black liquor and biomass gasification technology both pulp mills and integrated pulp and paper mills can potentially become net electricity exporters while at the same time removing CO2 from the atmosphere on a net basis. Furthermore, cost curves are constructed, which show how the cost of CO2 capture and storage in pulp and paper mills depends on system configuration and the distance that the CO2 must be transported to injection sites. The assessment shows that systems based on black liquor and biomass gasification with CO2 capture in integrated pulp and paper mills remove CO2 most cost-effectively.