Are you currently working? If you are, request a p45 when you leave and hand it to your new employer. Most employers issue a p45 as a matter of course but do tell them them if you have a new address.
If you're not currently employed complete a form 12 A - google this. You will need your new employers tax number.
You will get temp tax credits for 4 weeks anyway so that should allow any delays.