A method includes receiving an authentication certificate of a voice mail account holder and/or an authentication certificate of a caller wanting to leave a voice mail message the holders' voice mail account. A voice mail apparatus that provides voice mail service for the voice mail account holder performs such receiving. The account holder and/or the caller are authenticated after receiving the authentication certificate of the party being authenticated. Authenticating the account holder and/or the caller is performed using authentication information contained within the respective certificate. After such authentication is successfully performed, a voice mail message record can be created in the account of the account holder. Such creating includes allowing the caller to store the message in the account of the account holder in addition to associating authenticated identification information of the caller with the message and/or providing authenticated identification of the account holder to the caller.