Despite a total budget increase for rural development in the new programming period (2007- 2013), for most older Member States in the now expanded European Union the multi-annual spending plan for the period 2007-2013 predicts a substantial decrease of the budget for rural development and thus for agri-environmental schemes (AESs). It can be assumed that nothing or only part of this loss could be compensated by national funds in most countries. Therefore designing more efficient national governance structures for AESs, which decrease public transaction costs (TCs), would be an appropriate answer to this problem. The objective of this paper is to define the factors influencing these public TCs, because then appropriate action can be taken to reduce them. A statistical analysis with a proxy for public TCs is combined with an analysis of the perception on public TCs influencing factors of the stakeholders involved (not including farmers). The research showed that mainly scheme related factors are perceived to be important, although the governance structure, institutional environment and trust also play a role. High public TCs are however not necessarily a problem, if they would lead to a higher environmental effectiveness of the schemes. It is important to pay attention to the heterogeneity of the natural environment and on the basis of that decide for a more centralised or decentralised approach to AES design.