Data protection in the public sector has suffered from a number of high profile breaches over the last decade, revealing a culture of weak compliance, especially in comparison with that in the private sector. This article examines certain factors which make public sector data processing distinct, and how the lack of clarity regarding the routes to legitimate processing may be exacerbating these problems. By closely examining the jurisprudence regarding Schedule 2 of the Data Protection Act 1998, which provides the legitimate bases for data processing, we reveal the current problems public sector data controllers face in determining whether their processing is “necessary” and therefore legitimate. We determine that the test of necessity is reliant on proportionality, requiring the interest in processing the personal data to be balanced against the data subjects’ data protection and privacy interests. This in turn requires a detailed consideration of the public interests at stake, in providing the public services and respecting the personal data involved. We conclude by providing a structured and coherent three-step test for data controllers to apply in reaching their decision. This test focuses on the critical issues in balancing the competing interests, enabling data controllers to take a principle-based decision as to whether or not their processing is indeed in the public interest, proportionate and necessary – and therefore ultimately legitimate. This three-step test offers greater clarity for data controllers, which in turn should enhance the rigour of their data processing, thereby strengthening the data protection culture and benefiting data controllers, data subjects, and the public at large.