The article addresses organizational legitimacy in the public services, conducting an analysis of the records of the Office of the Police Ombudsman for Northern Ireland (OPONI) 2000-2018. A framework of organizational legitimacy provides a basis for examining OPONI’s record with respect to fulfilment of purpose, administrative efficiency and outcomes. Results suggest that OPONI needs to adjust to changing societal circumstances in Northern Ireland to sustain its role in persuading the people that policing is both fair and appropriate. A strategic reset is required given the diminished number of complaints cases linked to political conflict in order to avoid inadvertently destabilizing the post-conflict governance of policing.