The Kyoto Protocol is the first international environmental agreement that sets legally binding greenhouse gas emissions targets and timetables for Annex I countries. It incorporates emissions trading and two project-based flexibility mechanisms, namely joint implementation and the clean development mechanism to help Annex I countries to meet their Kyoto targets at a lower overall cost. This paper aims to estimate the size of the potential market for all three flexibility mechanisms under the Kyoto Protocol over the first commitment period 2008-2012, both on the demand side and on the supply side. Taking the year 2010 as representative of the first commitment period and based on the national communications from 35 Annex I countries, the paper first estimates the potential demand in the greenhouse gas offset market. We show that for most of the OECD countries excluding the EU, their Kyoto targets are stringent than they appear at first glance. Then, the paper addresses supplementarity constraints and provides a quantitative assessment of the implications of the EU proposal for concrete ceilings on the use of flexibility mechanisms for the division of abatement actions at home and abroad. Our results suggest that although the aggregate allowed acquisitions for the Annex I countries as a whole in 2010 from all three flexibility mechanisms under the two alternatives are well below 50% of the difference between the projected baseline emissions and the target in 2010, the proposed restrictions to each Annex I country vary, in some case even substantially. Finally, using the 12-region’s marginal abatement cost-based model, the paper estimates the contributions of three flexibility mechanisms to meet the total emissions reductions required of Annex I countries under the four trading scenarios, respectively. Our results clearly demonstrate that the fewer the restrictions on trading the gains from trading are greater. The gains are unevenly distributed, however, with Annex I countries that have the highest autarkic marginal abatement costs tending to benefit the most. With respect to non-Annex I countries, their net gains are highest when trading in hot air is not allowed. Because of a great deal of low-cost abatement opportunities available in the energy sectors of China and India and their sheer sizes of population, we found that the two countries account for about three-quarters of the total non-Annex I countries’ exported permits to the Annex I regions.