Computer storage media may have stored thereon a voicemail application. The voicemail application may be configured to determine whether messages in a voicemail box meet a preservation criterion. If the messages do meet the preservation criterion, the voicemail application may be configured to cause a replica of at least one of the messages to be made and stored outside of the voicemail box. After a message is replicated successfully, it may be deleted from the voice mail box.