See the post above yours. You will need to get a residency permit before signing up for insurance. Actually you can start both processes as soon as you arrive and are working. The permit takes about two months or more to receive, but the insurance company will insure you from the time your job starts if you contact them when you arrive and start working.
At least this is how it worked for me. Others might have a different story.
Good luck!