Understanding the specific relationships between ecological and socioeconomic conditions and marine tenure is likely to contribute to successful functioning of self-governance institutions for common-pool resources. Complex interrelationships of factors influencing fishing activities of coastal communities and implementation of customary marine tenure over their waters can be represented in a Bayesian belief network model. We developed a Bayesian belief network model that includes the links between factors for fishing communities in the Kei Islands in Indonesia, based on indepth local surveys. Our results showed that the cumulative impacts of multiple factors on key social, economic, and environmental outcomes can be much larger than the impact from a single source, which implies that management or policy intervention could be more effective when addressing multiple factors simultaneously. The local community's perception of fish stock abundance trends was the single most important factor influencing social, economic, and environmental outcomes of their community-based management system. The frequency of which outsiders were sighted in territorial waters was strongly (negatively) linked to weak or strong implementation of a customary tenure (Sasi) and the occurrence of intervillage and intravillage conflict. Ecological variables also drive these conflicts, which illustrates the close connection between ecological and social outcomes, and the importance of considering social-ecological systems as a whole.