> You need a work permit to get a job, not the other way around

To legally get a job yes, but that tends to not be super effective at stopping people, and even if the job itself is illegal, it can count as something that links you to the society where you want to regularize your situation.

Heavy "it depends on the country" since we're talking Europe-wide here.