This page takes you through the process.
I went through this a few months ago, when I was still using an old email address for my AppleID account. It was from the business where I was working at the time that I created the AppleID account. I kept using the account, even though the email account was long dead (business closed). When I had a problem, I could not successfully authenticate the account, because the email address in the account name was not available. I was ultimately locked out of my AppleID account, because of too many attempts with incorrect name/pw. My only choice was to call AppleCare, who reset my account, the process took me several days before I could get everything that I needed, and a couple of call-backs to AppleCare for support.
Additionally, I had all kinds of problems because I could no longer remember my account security responses.
You should not have a problem changing your AppleID, if the OLD email account is still one that you can use (still an active account)
Good luck!