A puzzle in the literature on the formation of coalitions supporting International Environmental Agreements (IEAs) is that if an IEA leads to substantial gains, then it will not be supported by many countries. The non-cooperative game theoretic literature highlights the “small coalitions” puzzle by which only a small number of countries are willing to sign an environmental convention. In these models, a global coalition comprising all countries and generating significant benefits is not sustainable. Moreover they indicate that greater the number of countries in the coalition, higher the incentive of signatories to not respect their engagement. The present paper resolves this puzzle by introducing social externalities, in order to explain why some treaties can be sustained by nearly all countries, while others can be supported only by a handful.