Se  seu email for regido por um provedor como o Google,MSN, UOL, etc.,  ou seja, um webmail os seus contatos ficam arquivados no servidor do provedor e você deverá entrar em contato com ele para descobrir qual a política da empresa em relação a back-up de contatos. Já quando seu email for uma cópia de email locada no computador, chamamos isto de POP3, por exemplo quando você utiliza Outlook,  ai depende do back-up da sua máquina, para salvar seus contatos no Outlook, vá em contatos, selecione todos, Arquivos, Importar e Exportar e selecione qual tipo de arquivo você quer gerar. Desta maneira você possuirá um arquivo com todos os seus contatos de email com você.
Lembre-se de modificar sua senha regurlamente, pois muitas vezes alguns ataques de vírus ou pessoas mal intencionadas podem invador sua conta e apagar seus contatos. Veja também, como escolho senhas seguras?