Stein began performing on the tenor saxophone in the early 1940s in New York City. As a teen he frequently sat in with Don Byas, whom he considered a mentor, and Erroll Garner, at The Three Deuces on 52nd Street. In 1945 he was featured in concert with pianist Teddy Wilson at Town Hall (although he had recently completed high school, he was billed as a high school student to make more of a sensation) on the same bill with Byas, Stuff Smith, and Charlie Parker. During the same year, Stein recorded with Doc Pomus, Tab Smith and Leonard Feather. He went on to work with Gene Krupa, Buddy Morrow, Les Elgart, Artie Shaw, Charles Mingus, Rudy Williams, Roy Haynes, Georgie Auld, Claude Thornhill, J. C. Heard and others. He also played the alto saxophone, recording on it with Al Cohn on Broadway (1954), in his own session with Warren Fitzgerald, Bob Dorough, Paul Motian and Alphonso Cotton (1955), on The Teddy Charles Tentet album (1956), and as one of the Four Altos with Juilliard buddy Phil Woods, Sahib Shihab and Gene Quill (1957). The record made with Fitzgerald was reissued decades later after becoming something of a cult classic in Japan.
He studied at Juilliard during 1950-51. During his stint in the Army jazz band in Japan during the Korean War (1951–1953), he was a regular member of Toshiko Akiyoshi's quartet. When he decided to go back to college in the late 50's he realized that the GI bill would not cover the cost of completing his degree at Juilliard, so he switched to Manhattan School of Music, where he achieved his master's degree in 1960. Stein embarked on a career as an educator, while continuing to perform regularly. During the '60's he taught in public schools in New York and California. Starting in the 70's, he taught at Stanford University, Mills College, University of California at San Francisco and San Francisco State University, as well as privately. During the late 70's and early 80's he taught in Jamey Aebersold workshops around the world.
During the mid-60's he moved back and forth between the East and West Coasts. In 1968 he moved out West for good, living first in Las Vegas, then in Seattle, and finally settling in the Bay Area in California in 1971, where he remained for the rest of his life. Some of the musicians he played with in this period include Benny Carter, Chick Corea, Sammy Davis Jr., Kenny Dorham, James Brown, Kenny Drew, Elvin Jones, Louis Hayes, Bill Evans, Joe Henderson, Joe Farrell, Nancy Wilson, Jessica Williams, and Rob Schneiderman. He led his own quartet during the 70's and 80's, Plank 'n Stein, featuring Al Plank on piano; later incarnations of his quartet were eponymous. In the late 80's and early '90's he made several solo tours of Europe, playing in France, Germany, and Italy; his daughter, singer Jennie Stein, joined him for one tour in Italy, and as a guest artist with him on a recording made there, Doctor in Jazz (1991).
Spirit! (his first recording as a leader since 1955) was recorded and released in 2006, featuring his working ensemble of pianist Lee Bloom, bassist John Wiitala and drummer Danny Spencer.
His father, Ralph Stein, was born Raphael Eisenstein in Dvinsk, Russia (now Daugavpils, Latvia) in 1898; his surname was shortened at some point during his youth after emigrating to the U.S. His mother, Jeanette Weiss, the daughter of Hungarian immigrants, was born in New York City in 1903. He married singer Shae Bevan in 1957; they divorced in 1978, and he did not remarry. They had three children: Greg (b. 1957), Jennie (b. 1959), and Naomi (b. 1968). All three children have followed in his footsteps as artists and educators in their respective fields. He had three grandchildren: Rebecca, the daughter of Jennie, b. 1989; Madelyn, b. 2008, (a few months after his death), and Benjamin, b. 2010, both children of Naomi.
He was still active teaching and performing until just a few months before his death.
- Hal Stein-Warren Fitzgerald Quintet (Progressive, 1955)
- Spirit! (GuideTone Media, 2006)
With Teddy Charles
With Al Cohn
- Broadway (Progressive, 1954)
With Giorgio Diaferia
- Doctor in Jazz (Splasc(H) Records, 1991)
- Blues in the Red (1945)
- Four Altos (Prestige, 1957)
- The Biographical Encyclopedia of Jazz by Leonard Feather, Ira Gitler
- Obituary from the SF Chronicle