To change your address with Medicare, you must contact your local Social Security office and verify your identity. From there, they can change your address on file by answering a few simple questions and providing supporting documentation.
If you have multiple addresses, you must provide your permanent residence. This is determined by where you spend most of your time throughout the year.