The highlands of Eastern Africa are characterized by high population densities and tightly coupled interactions between adjacent landscape units and users. Effective formal or informal natural resource governance is necessary to mitigate the potential negative social and environmental effects of individuals' behavior. Yet many natural resource management and development problems that require or benefit from collective solutions remain unresolved (German et al. Environ Dev Sustain 8: 535-552, 2006a; German et al. 2006b; German et al. Q J Int Agr 47(3): 191-216, 2008). We argue that many of the more intractable problems in improving governance stem from the trade-offs that underlie them, which may include a loss of livelihood options for at least some households, leading to governance break down. Following a brief introduction to natural resource management and governance in Eastern Africa, we analyze the results of participatory by-law deliberations by distilling the restrictions proposed governance reforms pose to certain local stakeholders. We recommend that future policy for improved landscape governance couple institutional reforms with livelihood alternatives that reduce the burden of good governance on households.