Andy Sheppard was born on January 20, 1957, in Warminster, Wiltshire, England, and grew up around Bristol. He did not take up music until he was 19 and planning to go to art college; listening to John Coltrane changed his direction, and within three weeks of getting his first saxophone he was playing in public. His first regular band was Sphere, a Salisbury-based quartet with the pianist Geoff Williams and the bassist Pete Maxfield, which made the albums Sphere (1981) and Present Tense (1985) for Cadillac Records. He never had a formal musical education.

In the early 1980s he worked the clubs of Britain and Europe and played with the pianist Keith Tippett and with world-music groups. He spent time in Paris, where he played with the performance band Urban Sax and the big band Lumière, and his credits from those years include Judie Tzuke's Ritmo (1983) and Freur's Doot-Doot (1983). Back in England in the mid-1980s he played often in Bristol's Old Profanity Showboat for Vivian Stanshall and Ki Longfellow-Stanshall. After winning a jazz competition in 1986 he signed with Antilles, and his debut, Andy Sheppard (1987), was produced by Steve Swallow, with Randy Brecker guesting on three tracks. It brought him the Best Newcomer prize at the 1987 British Jazz Awards and Best Instrumentalist the following year.

In 1987 he joined George Russell's Living Time Orchestra and toured with Gil Evans, and he plays tenor saxophone on Golden Hair (1989), Evans's record with Laurent Cugny and Cugny's Big Band Lumière. His second album, Introductions in the Dark (1989), entered the UK pop chart, unusual for a jazz record, and earned him Best Album and Best Instrumentalist at the 1989 British Jazz Awards, television documentaries from the BBC and HTV, and a world tour that included Outer Mongolia, where his group was the first Western jazz band to play. Soft on the Inside (1990) was a big-band project with the drummer Han Bennink, the trumpeter Claude Deppa and the trombonist Gary Valente among its players; the core of that band became In Co-Motion, with the keyboardist Steve Lodder and the bassist Sylvan Richardson, and recorded an album of that name in 1991. A move to Blue Note produced Rhythm Method (1993), made with an enlarged Big Co-Motion, and the live Delivery Suite (1994), recorded at Ronnie Scott's club in London.

His longest partnership began in 1989 with Carla Bley, on whose Fleur Carnivore he played tenor saxophone and clarinet. He stayed on in her big bands (The Very Big Carla Bley Band, 1991; Big Band Theory, 1993; The Carla Bley Big Band Goes to Church, 1996) and in the trio with Bley and Steve Swallow that recorded Songs with Legs in May 1994. The quartet The Lost Chords, with the drummer Billy Drummond, made The Lost Chords (recorded October 2003) and, with the trumpeter Paolo Fresu, The Lost Chords Find Paolo Fresu (2007). The trio returned on ECM with Trios (2013), Andando el Tiempo (2016) and Life Goes On (recorded May 2019, released February 14, 2020), the last album Bley made before her death in October 2023.

Between the Blue Note and ECM years he recorded Inclassificable (1995) with the Brazilian percussionist Naná Vasconcelos and Steve Lodder, Moving Image (1996), television scores written with Lodder, and four albums for the British label Provocateur: Learning to Wave (1998), Dancing Man & Woman (2000, with Steve Swallow and the tabla player Kuljit Bhamra as guests), Nocturnal Tourist (2001) and P.S. (2003, a duo record with the guitarist John Parricelli). He wrote Music for a New Crossing (2001) with the Northumbrian piper Kathryn Tickell for the opening of the Gateshead Millennium Bridge, and a fanfare for 200 local saxophonists, The Living Bridge, marking the 200th anniversary of Isambard Kingdom Brunel's birth, which grew into the saxophone-choir project Saxophone Massive. He also played on John Martyn's Cooltide (1991) and Couldn't Love You More (1992) and recorded duo albums with the pianists Joanna MacGregor and Rita Marcotulli.

ECM signed him as a leader for Movements in Colour (recorded February 2008, released April 2009), a quintet record with the guitarists John Parricelli and Eivind Aarset, the bassist Arild Andersen and Kuljit Bhamra. Trio Libero (2012) paired him with the double bassist Michel Benita and the drummer Sebastian Rochford, and adding Aarset made the quartet of Surrounded by Sea (2015) and Romaria (2018, recorded April 2017). The University of Bristol awarded him an honorary Doctor of Music in 2019. He has since recorded with the Norwegian pianist Espen Eriksen's trio (Perfectly Unhappy, 2018, and As Good as It Gets, 2023) and, with Marcotulli and Benita, Salt Catchers (ECM, released September 11, 2026), a trio album recorded in Lugano in March 2025 that holds eight Sheppard originals and one piece by Bley.

Sheppard plays tenor and soprano saxophones with a singing, melody-first sound, and he came to the instrument through the records of John Coltrane. AllMusic files his work under post-bop and modern creative jazz. His own biography describes a lyrical writing style combined with rhythms drawn from India, Africa and South America, which accounts for the tabla of Kuljit Bhamra and Sharda Sahai on his Provocateur albums and the percussion of Naná Vasconcelos on Inclassificable, a record John Fordham of The Guardian praised in April 1995 for its unhurried, freewheeling interplay. His ECM records lean toward chamber-like space: Eivind Aarset's guitar drones and electronics sit under his lines on the quartet albums, and Sheppard has described the quartet as the next step on from the improvising Trio Libero. He has also worked with samples and loops (Nocturnal Tourist, 2001, weaves street sounds and spoken word into his saxophone improvisations), written for big band, chamber orchestra and saxophone choir, and says he has composed more than 350 works. His long association with Carla Bley, who composed all the music on their trio albums, gave him decades as a featured soloist in another composer's music.