The nature of Indonesian Government spreads over 70 sectoral and 530 regional government agencies in a very vast geographical area. Hence, to maintain the quality of government services (G2G, G2B, G2C) post such a challenge. These services still scattered among government agencies with silo system. A lot of resources being waste, synchronization is lacking, and interoperability is impossible. Over all government performances are declined and bureaucracy reform is slowing down. This study proposes cloud-based e-government architecture. The architecture consists of six layers: user, access, service, management, virtualization, and infrastructure layers. The access layers accommodate various technological access devices in order to widening users' access. Initial experimental result shows that the implementation of cloud-based e-government architecture can improve cost-saving of Information and Communication Technology (ICT) investment.