This paper applies the probabilistic approach developed by Daraio and Simar (2005, 2007a, 2007b) in order to develop conditional and unconditional Data Envelopment Analysis (DEA) models for the measurement of countries’ environmental efficiency levels for a sample of 110 countries in 2007. In order to capture the effect of countries compliance with the Kyoto Protocol Agreement (KPA) policies, we condition first the years since a country has signed the KPA until 2007 and secondly the obliged percentage level of countries’ emission reductions.