I spent some time working in the UK. At that time it was illegal for a company to employ you unless you have a National Insurance Number, but one of the requirements to getting one of these numbers was having an employer. About the only to get one was to find an employer who was willing to let you work without a number on the understanding that you would then get one pretty quick (which of course then requires taking a full day off work, or two in my case)

Note: This was my experience in the late 90's. May be different now.