This paper presents a Trust Model for e-Government implementation. In the first part of the paper, the trust definition from different points of view (psychology, philosophy, linguistic, sociology, and mathematics) was presented. Most people think that to build trust between the government and its customers or citizens, one must start by implementing IT Security and some kinds of Customer Relationship Management (CRM) systems and that will lead to a full customer trust. However, this was not always true; most citizens or customers do not have positive attitudes toward their governments for political reasons, social reasons, and other reasons. The second part of the paper shows the main elements of trust with some examples. The last part discusses the proposed e-Government trust model and shows that trust was a multidimensional issue.Each part was fully integrated with the others in a certain relationship that formulates trust. The main building blocks of trust are: IT security, process automation, policies and procedures, social and culture practices, and legislation. This model represents a suitable guideline for any government who wishes to build or rebuild trust with its customers. It is necessary to use modern technologies to complete the trust architecture.