I'm surprised this is illegal. I worked for one company, and was offered a job by another. However, after accepting the offer, their legal department came back

I'm surprised this is illegal. I worked for one company, and was offered a job by another. However, after accepting the offer, their legal department came back to me and said they could not hire me after all, due to having an agreement with my current employer that they cannot hire an employee away from the other within a two year period. My understanding was that this was a contractual agreement between the two companies. How can they have a contract for this if it is illegal, is it different than what Apple and Google did?