The public sector, worldwide, is pressured to be more innovative in order to address the challenges of raising efficiency, providing solutions to an increasingly demanding citizenry, and enhancing services to industry in a progressively more complex environment that is fraught with unpredictability and tight budgetary constraints. These challenges demand systemic reforms to, among others, organizations, legislations and regulations, procedures and protocols. This paper presents a case study that involves organizational innovation in Malaysia, PEMUDAH, which seeks to enhance the public sector’s delivery system in order to better facilitate business. The case study reveals that the key factors contributing to the success of this innovation include, among others, political commitment, sustained leadership and ownership on the initiatives by all the stakeholders. The paper demonstrates that, with commitment and leadership, the innovation potentials of the public sector can be ignited for the benefit of all parties.