Bill McHenry was born in 1972 in Blue Hill, Maine, into a musical household: his mother is a pianist, and by his own account he is a great-great-grandson of the composer Horatio Parker, who taught at Yale and, most famously, flunked a student named Charles Ives. McHenry started on saxophone at ten. In 1986, at fourteen, he entered Michigan's Interlochen Arts Academy, and in 1990 he went on to the New England Conservatory in Boston, where he studied with George Garzone, Jimmy Giuffre, and John McNeil.

He moved to New York in the fall of 1992 and worked day jobs while getting established on the scene. During part of 1996 he lived in Barcelona, splitting time between the two cities with his sister Mary and his high school friend, the pianist Ben Waltzer; the Fresh Sound label there released a live album he made with Waltzer, Jazz Is Where You Find It. Back in New York, he studied long-tone production privately with Dewey Redman, a period he has credited with shaping his tone and musical identity. His debut as a leader, Rest Stop (Fresh Sound, 1997/98), paired him with guitarist Ben Monder, bassist Chris Higgins, and drummer Dan Rieser. The follow-up, Graphic (Fresh Sound, 1999), with Monder, bassist Reid Anderson, and drummer Gerald Cleaver, was named one of the New York Times critic Ben Ratliff's ten "alternative picks" of the year. Ratliff later wrote that McHenry "can play with un-orthodox structure and get as free as you want, but he maintains a ripe, lovely tone straight out of the 1950s," calling him lyrical in a way few players earn the word.

McHenry's working quartet with Monder and Anderson took on drummer Paul Motian in 2002, a pairing that led to repeat engagements at the Village Vanguard and two more albums: Bill McHenry Quartet Featuring Paul Motian (Fresh Sound, 2003) and, later, Roses (Sunnyside, 2007), both again with Monder and Anderson. Ghosts of the Sun (Sunnyside, 2011) kept Motian and Monder and added bassist Reid Anderson as producer. He has also led two duo records with the older trumpeter John McNeil, Rediscovery (2008) and Chill Morn He Climb Jenny (2010), both on Sunnyside, and a guitar-and-sax duo with Monder, Bloom (2010, Sunnyside). La Peur du Vide (Sunnyside, 2012) brought together bassist Eric Revis, pianist Orrin Evans, and drummer Andrew Cyrille. In 2014 he formed Us Free, a collaborative trio with bassist Henry Grimes and Cyrille, recording Fish Stories (Fresh Sound New Talent) with Grimes doubling on violin. Proximity (Sunnyside, 2016), a duo record with Cyrille recorded in Brooklyn in November 2014, was reviewed in DownBeat. His catalogue since has included the trio record Off the Cuff (2018) with Swiss saxophonist Domenic Landolf, bassist Bänz Oester, and drummer Jorge Rossy; the trio Ben Entrada La Nit (2018, Fresh Sound) with Revis and drummer R.J. Miller; and Solo Bill McHenry (2018, Underpool), recorded unaccompanied in Barcelona.

As a sideman, McHenry has been a recurring member of pianist and composer Guillermo Klein's Los Guachos big band since the late 1990s, appearing on Los Guachos II (1999), Los Guachos III (2002), Filtros (2008), Live at the Village Vanguard (2014), and Los Guachos V (2016), several of them reviewed in DownBeat. He has also recorded with bassist Chris Lightcap's Quartet, vocalist Rebecca Martin, bassist/composer Reid Anderson outside their own quartet work, and drummer Ethan Iverson's early trio Live at Smalls (2000), with Reid Anderson and Jeff Williams. His sideman credits also include a single track, "My Dear Country," on Norah Jones's Not Too Late (2007, Blue Note), and later work with bassist Eric Revis's own groups: the two-tenor quartet on In Memory of Things Yet Seen (2014), alongside saxophonist Darius Jones, and the quintet on Slipknots Through a Looking Glass (2020, Pyroclastic Records). In July 2015, trumpeter Avishai Cohen brought McHenry into the studio at Studios La Buissonne in the south of France for his ECM debut, Into the Silence (2016), where McHenry's tenor joins the core quartet of Cohen, pianist Yonathan Avishai, bassist Eric Revis, and drummer Nasheet Waits on several of the album's six pieces, produced by Manfred Eicher.

McHenry's playing sits deliberately between two traditions that rarely share a bandstand: a warm, vocalized tenor tone descended from an older, pre-Coltrane school (Ben Ratliff traced it "straight out of the 1950s") wrapped around structures loose enough to satisfy the free players he has spent decades alongside. His studies with George Garzone and Jimmy Giuffre at the New England Conservatory, and his private work on long-tone production with Dewey Redman afterward, both point toward that tone-first conception. It is what let him hold the tenor chair in Paul Motian's exploratory quartet music and, in the same decade, co-lead a trio with two committed elders of the 1960s avant-garde, bassist Henry Grimes and drummer Andrew Cyrille, without the two contexts sounding like different players. His working relationship with Guillermo Klein's Los Guachos big band, spanning nearly two decades, has also placed him inside some of the more harmonically adventurous large-ensemble jazz composition of the period.