Question: how do you change your address on your national insurance number?
Answer: Online using CRA's MyAccount service. If you do not already have an account, you can register freely. ... 
By phone at 1 800 959-8281.
Mail or fax one of these two documents to your local tax centre: