The aim of this paper is to investigate, and to discuss the key critical factors that facilitate the successful implementation of E-government projects. The nature of this research is mainly qualitative. This investigation uses a single case study and data was mainly collected by means of semi-structured interviews and organisational documents from the Ministry of Higher Education in Oman. The research findings suggest that there are three paradigms which each include a set of factors that impacts the success of E-government success namely, organisational paradigm, technology paradigm and end-users paradigm. The authors believe that, this paper demonstrates an added value to the current literature on transformation of E-government and to E-government projects success, within the wider context of E-government implementation projects. Also the research will benefit organisations in the public sector, as it has identified main key success factors in E-government transformations and implementations.