Voice Message Communication Method and System

A system is disclosed which provides communication of recorded voice messages over a network among a plurality of users having voice communication devices. The system has a voice message server connected to the network, which includes a receiver which receives from a sending user's communication device a voice message signal including a header component and a recorded voice message component is stored at the server in association with the corresponding header. The header component identifies the sending user and an intended recipient user, and it is transmitted to the communication device of the intended recipient identified in the header component. The corresponding voice message component is transmitted to the recipient user's communication device in response to the recipient user's communication device requesting it. The recipient user may send a responsive voice message to the server addressed to the sending user.