Katz was born to Arnold and Angelina Katz and was raised in Paterson, Passaic County, New Jersey before moving with her family to Edgewater Park, Burlington County, New Jersey. Her father worked as a factory laborer in Paterson before getting a sales job in Burlington County, where he later served as mayor of Edgewater Park Township in 1982 and 1983. Katz attended Burlington County College and graduated from Rutgers University with a bachelor's degree in labor studies in 1981. In 1995, she received a master's degree from Rutgers in labor and employment relations. A year after graduating from Rutgers, she started as an organizer for the Communications Workers of America and rose through the ranks to become president of Local 1034 in 1999. Local 1034 was CWA's largest local union in the country with more than 16,000 members in both the public and private sector. Katz served as a Commissioner of the Public Employment Relations Commission for five years on an appointment by Governor Donald DiFrancesco. Katz enrolled at Seton Hall University School of Law in 2004 and graduated with a juris doctor four years later. She has been a visiting part-time lecturer at Rutgers and contributes to the "NJ Voices" blog on NJ.com. In May 2009, the radio stationWKXW announced that Katz would join the afternoon drive show "The Jersey Guys" in a series of appearances. In March 2010, Katz joined the Livingston, New Jerseylaw firm Fox & Fox LLP. She was "of counsel" to the firm, specializing in labor law. Katz has two children, Montana and Cooper McKim, with her ex-husband Larry McKim, a New Jersey artist.
Katz first met Jon Corzine in the spring of 1999, when he was running for the United States Senate. As Katz later recalled, Corzine offered her a job on his Senate campaign, but she declined the job offer. Corzine and Katz were soon dating, appearing in public as a couple in early 2002, shortly after Corzine's separation from his wife Joanne. Katz and Corzine lived together in Hoboken from April 2002 until their breakup in August 2004. Corzine gave Katz a $470,000 mortgage for her home in Alexandria Township, New Jersey, which he later forgave. Corzine was sworn in as governor in January 2006 and maintained a close friendship with Katz. A state ethics panel, responding to a complaint from Republican Bogota mayor Steve Lonegan, ruled in May 2007 that Katz's personal contact with Corzine during labor negotiations did not violate the governor's code of conduct. Separately, New Jersey Republican State Committee Chairman Tom Wilson filed a lawsuit to release all e-mail correspondence between Corzine and Katz during the contract negotiations. On May 30, 2008, New Jersey Superior Court Judge Paul Innes ruled that at least 745 pages of e-mail records should be made public, but Corzine's lawyers immediately appealed the decision. Corzine won his case on appeal, and on March 18, 2009, the New Jersey Supreme Court ruled that it would not hear arguments in the case, effectively ending the legal battle to make his e-mails with Katz public.
