The concept of electronic government has established as an effective mechanism for increasing government productivity and efficiency and a key enabler of citizen-centric services. In Gulf countries, public sector transformation efforts are focused towards increasing accessibility, availability, competitive advantage and enhancing services in civil administration. The Sultanate of Oman is one such example of Gulf countries where large investments have been made since 2003 to implement electronic services in the public sector. Using a qualitative research approach, this research attempts to answer the question why the progress of e-government has been slow in some governmental ministries, whereas other ministries have implemented e-government in a successful manner. The paper investigates the improvements that have been made to facilitate these electronic services in three public ministries and their resulting impact within the organisations. The results of the empirical study reveal some of the generic issues faced by the Omani government in implementing e-services and how other specific challenges faced by the individual ministries such as top management support, integration and IT staff skills and capabilities are impeding e-government in the Omani public sector.