Cloud computing essentially is a scalable, flexible and pay-per-use model for the way IT services are delivered. It can significantly improve the way a government functions, the services it provides to its citizens and institutions. This paper aims to explore the factors that influence adopting cloud computing as a part of public sector organizations’ alternatives to implement e-government services. Based on two dominant theories in the field of adoption of new technology, the Fit-Viability Model and Diffusion of Innovation Theory, a model is proposed. Data were gathered using a structured questionnaire with a sample of 296 IT staff employed in public organizations in Yemen. The results clarify the need to consider factors affecting two dimensions, fit and viability, to make a decision to adopt cloud computing in an e-government context. The fitness of cloud computing to e-government tasks is affected by factors such as relative advantage, compatibility, trialability and security, but is not affected by the complexity of the technology. On the other hand, the viability is influenced by economic factors (return on investment and asset specificity) and technological readiness (IT infrastructure and IT policy and regulations), while the results do not support the relation between the organizational factors such as top management support and cloud knowledge and viability.