The current literature on common-pool resources suggests that appropriators’ autonomy in determining access and harvesting rules is a pre-condition for successful local self-governance. Yet few studies have been done to examine how local communities that are faced with outside intrusion can regain such autonomy. This paper examines this issue by studying how two mountain tribal villages in Taiwan have attempted to rebuild their indigenous rules governing the use of their local stream fisheries. One village, Shan-Mei, has been more successful than the other village, Li-Chia, in restoring self-governance in fishery conservation. Shan-Mei’s relative success is explained by its villagers’ willingness and ability to develop mutually beneficial relationships with external stakeholders and to attain a negotiated autonomy from the larger society.