Klein was born in Newark, New Jersey and was of Hungarian Jewish descent. He married a woman named Betty, after he graduated from college. He first became well-known when he helped a singer, Bobby Darin, to recover money owed to him by his record label. Darin received a $100,000 check for unpaid royalties, and split it with Klein. Klein was called the "Robin Hood" of popular music, liked by artists but hated by the companies they worked for.