A computer implemented method and system is provided for exchanging voice messages between a sender and a recipient. A client component that allows the sender to create, address, and render the voice messages to the recipient using a graphical user interface is provided. A messaging server that enables interaction between the sender and the recipient is also provided. The sender records one or more voice messages and addresses the recorded voice messages on the client component by entering a recipient address or an arbitrary address. The client component transmits the recorded voice messages, the recipient address or the arbitrary address, and a client identifier to the messaging server. The messaging server resolves a recipient delivery address based on the arbitrary address. The messaging server transmits a delivery message comprising the recorded voice messages to the resolved recipient delivery address. The recipient responds to the recorded voice messages with response messages.