In this chapter, strategic leadership is investigated as a factor that influences e-governance change in the Ethiopian public service sector and the issue of the mediating effects of the organizational culture of digital literacy is explored. The research used a sample size of 396 respondents based on which sampling adequacy is determined The results obtained indicate that strategic leadership plays a major role in enhancing the adoption of e-governance mainly involving improvement of OC and promotion of digital literacy among members of the service sector. This chapter reveals the importance of building a supportive organization culture in facilitating the development of digital literacy that in the future enables positive e-governance practices. The chapter is a primary source to which policymakers and researchers concerned with the workings of the digital governance within an emerging economy can refer.