This study analyzes transaction costs occurred in the existing set-up of upstream-downstream relations and reward mechanisms of the watershed services in Sumatra, Indonesia. The rewards are manifested through property right reforms in terms of "recognition" and "loss of fear of eviction" among local communities to utilize land within the "protection forest", such as implemented under the community-based forestry management (CBFM) policy. The study sites of Sumber Jaya watershed in Sumatra, Indonesia has been notoriously known as a benchmark for conflict of watershed functions between the state and the society, and among stakeholders such as coffee growers, domestic water-users, hydroelectric power company, etc. Estimated transaction cost to implement the rewards is US$ 55 per household, a relatively high cost for rural standards. The component consists of costs of searching information (70%), organizing the group (27%), and enforcement of working rules and regulations (3%), implying a non-efficient economic organization of the society and non-clear policy structures at regional and national level. Roles of intermediaries such as NGO (national and international) are extremely important to implement the negotiation support system and develop multi- stakeholders strategy to reduce transaction costs, especially to ensure conflict resolutions, improve trusts and shared responsibility to achieve more sustainable resource management.