Which mail client do you use?
If it's IMAP, then you should already have your mail "backed up" on your computer. Just make sure you back up your home computer as well.
I use Apple's Mail.app and all of my messages are stored as files. If I were to change servers, I'd set up a new IMAP account, then sync my current mailboxes to the new account and then all my mail would be in my new account on the server.