E-Government continues to be recognized as a key strategy for improving the effectiveness of governmen services. It enables citizens, and government ministries to interact with one another through a new electronic channel that is unconstrained by the locations and schedules. However, realizing this vision is strictly based on the ability of multiple, independent and quite diverse computing systems owned and managed by different government ministries to be able to interact together across all ministerial boundaries. This ability is known as e-government interoperability. Achieving e-Government interoperability is not an easy task because ministries have built their computing systems independently that produce solutions relevant to their particular needs but without adequate attention to the need to interact (connect, exchange and re-use data) with other ministries systems. This results in a patchwork of heterogeneous computing solutions that have limited coherence and largely are uncoordinated. During the last few years, e-Government Interoperability has been an important research area in order to facilitate the seamless exchange of information across governmental ministries computing systems. To this direction, several approaches have been proposed through the adoption of standards or through architectures. However, merely adopting these approaches would be insufficient since these approaches are theoretical solution and/or technical focused and have their own limitatons. Whereas, e-Government interoperability has different software system levels to interoperate with other software system(s) associated with several strong barriers on the road to its achievement. Therefore, this problem requires more practical solution. In order to achieve e-Government interoperability this thesis presents an architecture and a methodology to help establishing interoperability in e-Government. Also, an interoperability framework is presented to overcome interoperability barriers and concerns. The proposed framework is inspired by other researcher's frameworks. The proposed methodology shows the main phases to follow to approach the developed service oriented e-Government architecture. This visualizes the whole e-Government low level system architecture that aims to solve the architectural problem in achieving seamless e-Government interoperability. Then, a case study is provided to demonstrate the applicability of the proposed architecture and methodology.