An integrated messaging system uses existing messaging systems to receive, store, retrieve and manage messages in media types and formats appropriate to each existing system using protocols which are specific to that system. Two or more systems are tightly coupled in that a message received in one system can be accessed from all other systems. Coordination between messaging systems is achieved by a synchronizer system running in one of the existing servers or in a stand-alone server. The synchronizer comprises a plurality of threads which sequentially examine corresponding mailboxes in each messaging system and update the message states in each system so that all message states correspond. In order to determine whether a message state has changed, the synchronizer maintains a state database which stores the state of each message in all messaging systems which are connected to the synchronizer. A further gatway thread is provided so that messages can be sent directly from one messaging system to another messaging system. The synchronizer is connected to each messaging system via a standard CMC interface so that it can log onto each messaging system as a trusted server and modify user's mailboxes without requiring a password.