There is little consensus of common understanding of innovation in bureaucratic organizations; thus, leading to minimal enhancement to the growth and execution of innovation in this sector. It is apparent that practitioners and scholars are not on the same page regarding public sector innovation research. The market innovation literature along with perspectives on public sector innovation showed that within any organization, an innovative culture must be supported by individuals in power. One major challenge for practitioners is to develop systems, processes, and climates that promote and demonstrate innovation and creativity. In other words, the development of a supportive climate for enhancing employees' innovative behaviour and creativity is not an option. While much public sector research is centred on why the public sector should change and what changes should be made, little is known about how to encourage the whole systems towards having greater innovation capacity. Public organizations are constantly under severe pressure to produce more value for their communities. The complex nature of the term innovation particularly in the government made it essential for public services to engage with the concept. In addition, key leadership behaviours and styles for managing and promoting innovation in the public sector is crucial part of this paper. The objective of this paper is to critically review academic publications in innovation and leadership in public sector organizations. From the review and analysis of literature, the paper determines what is required, and what constraints are imposed by organizational and environmental factors to nurturing or fostering a culture of innovation in the government sector. A conceptual framework is gradually developed based on the analysis and knowledge obtained from relevant literature. Hence, the researchers discuss achievable and indispensable factors that might promote or enhance a culture of innovation in the public sector. The comprehension provided is intended to support scholars and practitioners in highlighting critical issues necessary to promote a culture of innovation in the government sector. Although the paper is narrative or descriptive in nature and non-statistical, it can be used to enhance the understanding of innovation in public sector organizations.