The endless transformation of technological innovation requires greater collaboration of Information Communication and Technology (ICT) in various areas especially in public sectors. Many attempts have been made in improving the quality of E-Government services, one of it is adopting the cloud computing technology. Successful-implementation of cloud computing technology can benefit the public sector in many ways one of it is cost reduction. Most government organizations especially in the developing countries are committed in adopting the cloud technology based on the increased demands in cloud adoption in E-Government services. Unfortunately, despite all the benefits, the cloud computing technology raises some major risks. The success of implementation of cloud computing technology is determined by how well the government tackles the challenges. Therefore, this paper specifically surveyed the associated challenges of adopting Cloud Technology for E-Government by choosing Malaysia as the case study.