Born in Bow, East London, Winstone began singing in bands around Dagenham in the early 1960s, before joining Michael Garrick's band in 1968. Her first recording came the following year, with Joe Harriott. In 1971 she was voted top singer in the Melody Maker Jazz Poll. She recorded the album Edge of Time under her own name in 1972. Winstone contributed vocals to Ian Carr's Nucleus on that band's 1973 release Labyrinth, a jazz-rock concept album based on the Greek myth about the Minotaur.
Winstone has worked with many major European musicians and visiting Americans, as well as with most of her peers in British jazz, including Garrick, John Surman, Michael Gibbs, Mike Westbrook and her former husband, the pianist John Taylor. With Taylor and trumpeter Kenny Wheeler she performed and recorded three albums for ECM as a member of the trio Azimuth between 1977 and 1980; their CD How It Was Then… Never Again was given four stars by Down Beat magazine. In addition she made an album with the American pianist Jimmy Rowles (Well Kept Secret, 1993).
- 2007: MBE in the Queen's Birthday Honours, for services to music.
- 2009: Skoda Jazz Ahead Award in Bremen for her contribution to European Jazz.
- 2010: London Awards for Art and Performance.
- Hum-Dono (with Joe Harriott, Ian Carr and others 1969; EMI Columbia; never released on CD)
- Edge of Time (recorded 1970; Decca Records, 1972; re-released as a CD on the Disconforme label)
- Song For Someone (recorded 1973; psi0401)
- Somewhere Called Home (ECM, 1986)
- Well Kept Secret (with Jimmy Rowles; recorded 1993, Enodoc Records)
- Manhattan in the Rain (with Steve Gray, piano, Chris Laurence, bass, Tony Coe, tenor sax & clarinet; recorded 1997; Enodoc Records, 1998)
- Like Song, Like Weather (with John Taylor, piano; recorded 1998; Enodoc)
- 4 in Perspective (with Fred Hersch, piano, Kenny Wheeler, trumpet & flugelhorn, Paul Clarvis, percussion; recorded 1999; Village Life 00909VL)
- Chamber Music (with Glauco Venier, piano, and Klaus Gesing, sop. sax and bass clarinet; recorded 2002; Universal)
- Amoroso...Only More So (recorded 2006; with Stan Tracey trio and Bobby Wellins; Trio Records)
- Distances (with Glauco Venier, piano, and Klaus Gesing, sop. sax and bass clarinet; recorded 2007, ECM)
- Stories Yet To Tell (with Glauco Venier, piano, and Klaus Gesing, sop. sax and bass clarinet; recorded 2009, ECM)
- Dance Without Answer (ECM, 2013)
- Azimuth (ECM, 1977)
- The Touchstone (ECM, 1978)
- Départ (with Ralph Towner) (ECM, 1979)
- Azimuth '85 (ECM, 1985)
- How It Was Then... Never Again (ECM, 1995)
With Eberhard Weber
- Fluid Rustle (ECM, 1979)
- Norma Winstone - official website of the singer.
- ECM - album catalog of the singer on ECM Records.
- Norma Winstone on BlueMusicGroup.com