Stein was born to Jewish parents in Brooklyn, New York. He grew up in the Midwood section of Brooklyn, and attended Midwood High School in Brooklyn, but was expelled for wearing long hair. While in Blondie, Stein and Harry maintained a romantic relationship but never married. In 1989, the couple went their separate ways but have continued to work together on a professional basis. Stein was co-host of "TV Party", a public-access television cable TV show in New York City, that ran from 1978 to 1982.