The means through which governments deliver services and the way they operate may be considerably enhanced through cloud computing. It can help to address e-government implementation challenges and revolutionize e-government systems in terms of cost savings and the professional use of resources. The aim of this paper is to analyze the importance and performance of the factors that influence the fitness of cloud computing fore-government implementation. This paper integrates the task technology fit model with the diffusion of innovation theory to address this issue. Yemeni public institutions were identified as sources for data collection and 292 information technology employees participated as sample respondents for a structured questionnaire. Security, compatibility, relative advantage, and tasks were the variables found to affect the fitness of cloud computing for e-government activities. However, no impact was seen from the standpoints of trialability and complexity of the technology. In terms of assessing the fitness of cloud computing for e-government services, a greater understanding among policy formulators was sought through the importance-performance matrix analysis (IPMA). The results of IPMA can help identifying areas for strategic focus to assess cloud computing as an alternative technology to implement e-government services.