In the context of transformation in the governance of public service sectors, performance criteria have mainly focused on efficiency and effectiveness. However, relying on such output oriented performance criteria in public service sectors may lead to inequalities in service provision and a fragmented polity. Moreover, legitimacy is becoming a central concern in the governance of public service sectors due to the increasing involvement of private actors. This paper proposes to add legitimacy to efficiency and effectiveness and to use these as three criteria for analyzing the performance of governance in a public service sector. This paper elaborates the analytic foundations of these three criteria via two theories: governance theory and new institutional economics. The aim is to create an analytical framework through which governance performance in public service sectors can be evaluated in terms of legitimacy, efficiency and effectiveness.