The paper presents the development of a dependable messaging infrastructure for Electronic Government. Based on a few simple concepts like messages, members and channels, the infrastructure was developed to facilitate the exchange of messages by government agencies in a dependable and automated way. The dependability requirement was addressed on various levels: design, development and application. Considering design, the infrastructure comprises a small core offering plain messaging services, a repository of extensions to provide additional services, and a development framework to rigorously specify, implement and verify messaging extensions. Considering development, the infrastructure was build through rigorous use of modeling and analysis in various development stages. Considering applications, government agencies can use the infrastructure to exchange messages through carefully managed logical communication channels and the prudent use of necessary extensions, including extensions to implement required security measures. The paper presents the development and explains why the outcome satisfies the dependability requirement.