A method (200) for managing voicemail messages for a visual voicemail system (102) can include establishing a secure data session (212) between a voicemail system (102) and a mobile device (118). The voicemail system (102) can receive a voicemail message (202) that is directed to a voicemail account associated with a voicemail subscriber. The voicemail system (102) can generate a notification message and can send the notification message (208) to the mobile device (118) that is associated with the voicemail account that received the voicemail message. In response to the notification message, the mobile device (102) can generate and send a first request for voicemail message header information (234). The voicemail system (118) can send the requested voicemail message header information (236) to the mobile device (102) and, in response, receive a second request for at least one voicemail message (238). The voicemail message can send at least a portion of the at least one voicemail message (240) to the mobile device (118).