Halley was born and raised in New York City. He is the son of Janice Halley, a registered nurse of Polish ancestry, and Rudolph Halley, an attorney and politician of German-Austrian Jewish descent. In 1951, Rudolph "became an instant celebrity," as Halley has said, while serving as chief prosecutor for the United States Senate Special Committee to Investigate Crime in Interstate Commerce, also known as the Kefauver Committee (after Senator Estes Kefauver). "This series of hearings with various colorful mobsters was broadcast on television all over the country," Halley notes. Rudolph was also assistant counsel to the wartime Truman Committee, investigating fraud and waste in defense contracting. He served as president of the New York City Council from 1951 to 1953, and ran for New York City Mayor in 1953. He passed away soon after at the age of forty-three, when Halley was three years old.