Depends on your jurisdiction. Sometimes hiring someone without verifying their right to work is a crime. (Or without registering with the tax authorities, or social security, or ensuring they have adequate breaks, or or or... paying someone to work for you is often something that involves quite a lot of responsibility, since the law often doesn't really contemplate private individuals doing it outside of the super-rich)
In that case you just hire via some kind of agency, who deal with the HR for you.
> is a crime
A legal wrong, generally, as in most cases it's not under criminal law.
In the UK it's criminal if you "have reasonable cause to believe" that there were issues with their immigration status. I don't know about other countries.