A voice message service provider enables users to access voice messages through a first access point for creating voice messages and a second access point for retrieving the created voice messages. In one implementation, a user calls the first access point to create a message, and the voice message provider indexes the created voice message with a message retrieval telephone number and one or more recipient identifiers. A notification message containing the message retrieval telephone number is sent to the intended recipient to provide notification of the voice message. The intended recipient may retrieve the voice message by calling the message retrieval number contained within the notification message and providing the recipient identifier. The voice message service provider identifies the voice message associated with the message retrieval number and recipient identifier and returns the voice message to the intended recipient.