Institutions are vital to the sustainability of social-ecological systems, balancing individual and group interests and coordinating responses to change. Ecological decline and social conflict in many places, however, indicate that our understanding and fostering of effective institutions for natural resource management is still lacking. We assess theoretical and methodological challenges facing positivist institutional analysis, focusing on natural resource governance according to Ostrom’s social-ecological systems (SES) framework. Rather than adding more variables, progress requires a clearer, more consistent approach to selecting, defining and measuring institutional elements; stronger links between theory and empirical research; a greater focus on mechanisms and causality; and the development and application of new methods, including quantitative approaches. Strengthening the connections between theory, models, and data suggests several promising avenues for advancing institutional analysis through the study of relationships between institutional structure, process, function, context, and outcomes.