In this paper we incorporate interdisciplinary New Institutional and Transaction Costs Economics, and suggest a framework for analysis of mechanisms of governance of agro-ecosystem services. First, we present a new approach for analysis and improvement of governance of agro-ecosystem services taking into account: the role of specific institutional environment (formal and informal rules, distribution, and enforcement of rights); behavioral characteristics of agents (preferences, bounded rationality, opportunism, risk aversion, trust); transactions costs associated with ecosystem services and their critical factors (uncertainty, frequency, asset specificity, appropriability); comparative efficiency of market, private, public, and hybrid modes of governance. Second, we identify the spectrum of market and private forms of governance of agro-ecosystem services (voluntary initiatives; market trade with eco-products; special contracts; collective actions; vertical integration), and evaluate their efficiency and potential. Next, we identify needs for public involvement in agro-ecosystem services, and assess comparative efficiency of alternative modes of public interventions (assistance, regulations, funding, taxing, provision, partnership, property right modernization). Finally, we analyze structure and efficiency of the governance of agro-ecosystems services in Zapadna Stara Planina in Bulgaria. Postcommunist transition and EU integration brought about significant changes in the state and governance of agro-ecosystems services. Newly evolved market, private, and public governance led to significant improvement of part of the agro-ecosystems services, introducing modern eco-standards and public support, enhancing environmental stewardship, disintensifying production, recovering landscape and traditional productions, diversifying quality, products, and services. Simultaneously, novel governance is associated with some new challenges such as unsustainable exploitation, lost biodiversity, land degradation, and water and air contamination. Implementation of EU common policies would have no desired impact on agro-ecosystem services unless special measures are taken to improve management of public programs, and extend public support to dominating small-scale and subsistence farms.