E-government is growing to a size that requires full attention from governments and demands collaboration and facilitation between private sectors and Non-Government Organizations (NGOs). In order to reach successful e-government applications, governments have to provide services to citizens, businesses and government agencies. In Jordan, e-government applications are limited to an informative goal; they essentially offer information and no services. Moreover, it is found that the traditional peer-to-peer integration of applications will result in a tightly coupled system that reduces the agility and expansibility of the E-Government system. This paper proposes a novel integration mechanism based on the web service of the Service Oriented Architecture (SOA) for the various E-government systems. We propose a stage model for E-Government interoperability based on Service Oriented Architecture (SOA). In addition, a framework for E-government based on SOA is proposed. The proposed architectures are being examined using case study in the context of implementing environmental license web service in the Jordanian ministry of environment.