Con once años obtiene su licenciatura de piano en el McGill Conservatory e inmediatamente, pasa a dirigir la orquesta de su liceo, y a tocar regularmente con su propio cuarteto en clubes de la ciudad. En 1949 sustituye a Oscar Peterson en varios locales, tras la marcha de este a Estados Unidos. En 1950 se traslada a Nueva York y estudia en la Juilliard School.

En 1953, graba su primer disco, acompañado por Charles Mingus y Art Blakey. Se traslada después a California, donde toca con Chet Baker. Después forma un trío junto a Billy Higgins y Charlie Haden, con el que tocará con Ornette Coleman y Don Cherry (1958) y con Scott LaFaro (1959). Ya en la década de 1960, tocará en los grupos de Mingus, Eric Dolphy, George Russell y Bill Evans, y formando tríos vanguardistas con Steve Swallow y Jimmy Giuffre (1962), y con Gary Peacock y Don Ellis (1963).

Colabora con la Jazz Composers Guild, junto con su esposa Carla Bley, separándose de ambas en 1964, aunque participa en el manifiesto del free jazz que se plasma en la "revolución de octubre de 1964", junto con Cecil Taylor y Archie Shepp. A partir de 1968 comienza a interesarse por los teclados electrónicos y los sintetizadores, trabajando junto a la cantante Annette Peacock, aunque desde mediados de la década de 1970 regresa al piano acústico en formato de solo. Ya en los años 1980, vuelve a tocar en cuarteto, con John Surman, Paul Motian y Bill Frisell.

En 1999 se publica su autobiografía, Stopping Time: Paul Bley and the Transformation of Jazz y, en 2003, la obra Time Will Tell: Conversations with Paul Bley. Un año después, en 2004, se publica en italiano el libro Paul Bley: la lógica del caso. En 2008, es nombrado miembro de la Orden de Canadá.^[2]​

Para muchos autores, Bley puede considerarse, junto a Bill Evans, como el "inventor" del trío de piano moderno, desarrollando una música con tendencia a desbordar el cuadro armónico, lo que aporta a sus grupos una ligereza y apertura de líneas en la que sus propios solos son la quintaesencia.^[3]​

Comenzó tocando bop, para luego incorporarse con decisión a la evolución del free jazz y la música de vanguardia, recalando finalmente en formas avanzadas de post bop.

Primeros sellos

• 1953: Introducing Paul Bley (Debut)
• 1954: Paul Bley (EmArcy)
• 1963: Footloose!, Savoy
• 1964: Turns, Savoy, (reeditado en 1988 en Improvising Artists)
• 1964: Barrage (con Marshall Allen, Dewey Johnson, Eddie Gomez, Milford Graves), ESP
• 1965: Closer (con Barry Altschul, Steve Swallow), ESP
• 1965: Touching, Fontana
• 1965: Blood, Fontana
• 1966: In Harlem - Blood, Polydor
• 1966: Ramblin, BYG
• 1968: Mr. Joy, Limelight
• 1973: Scorpio (con David Holland, Barry Altschul), Milestone

América

• 1971: The Fabulous Paul Bley Quintet (Grabado en vivo en el Hillcrest Club, Los Angeles, 1958)
• 1972: Improvisie

Freedom Records

• 1970: Dual Unity (con Annette Peacock, Han Bennink, Mario Pavone, Laurence Cook)^[4]​
• 1975: Copenhagen and Haarlem (Grabado en vivo entre 1965 y 1966)

Improvising Artists (Sello propiedad de Bley)

• 1974: Jaco
• 1975: Quiet Song (con Jimmy Giuffre y Bill Connors)
• 1975: Alone, Again
• 1975: Turning Point (con John Gilmore, Gary Peacock, Paul Motian), editado originalmente en Savoy, en monoaural , en marzo de 1964
• 1976: Virtuosi
• 1977: Japan Suite
• 1977: Coleman Classics Vol. 1
• 1977: Axis
• 1978: IAI Festival (con Giuffre / Konitz / Conners / Bley)

SteepleChase Records

• 1972: Solo Piano
• 1973: Paul Bley/NHØP (con Niels-Henning Ørsted Pedersen)
• 1985: Questions
• 1985: My Standard
• 1986: Live & Live Again
• 1987: Indian Summer
• 1988: Solo Piano
• 1988: The Nearness of You
• 1989: Rejoicing
• 1989: Bebopbebopbebopbebop
• 1991: Plays Carla Bley
• 1992: Caravan Suite
• 1992: At Copenhagen Jazz House
• 1993: If We May
• 1994: Speachless
• 1995: Reality Check
• 1998: Notes on Ornette

ECM

• 1970: Paul Bley with Gary Peacock
• 1971: Ballads
• 1972: Open, to Love
• 1986: Fragments
• 1987: The Paul Bley Quartet
• 1991: In the Evenings Out There
• 1994: Time Will Tell (con Evan Parker y Barre Phillips)
• 1999: Not Two, Not One (con Gary Peacock y Paul Motian)
• 2000: Sankt Gerold (con Evan Parker y Barre Phillips)
• 2007: Solo in Mondsee

Soul Note

• 1983: Tango Palace
• 1983: Sonor
• 1985: Hot (con John Scofield)
• 1987: Notes (con Paul Motian)
• 1988: Live at Sweet Basil (con John Abercrombie)
• 1990: Memoirs (con Charlie Haden y Paul Motian)
• 1992: Mindset (con Gary Peacock)
• 1994: Chaos

Justin Time Records

• 1987: Solo
• 1991: A Musing (con Jon Ballantyne)
• 1993: Sweet Time
• 1993: Double Time
• 1993: Know Time
• 1994: Outside In
• 1996: Touche (con Kenny Wheeler)
• 2001: Basics
• 2004: Nothing to Declare
• 2008: About Time

Owl

• 1983: Tears, Owl
• 1990: Partners (con Gary Peacock), Owl
• 1993: Homage to Carla, Owl

hatART

• 1992: Annette (con Franz Koglmann, Gary Peacock), hatART

Postcards Records

• 1994: Synth Thesis
• 1994: What If (con Bruce Ditmas como líder, John Abercrombie, Sam Rivers, Dominic Richards)
• 1996: Music for the Millennium (con Ralph Simon como líder, Gary Peacock, Julian Priester)

• BERENDT, Joachim E.: El Jazz: Origen y desarrollo. Fondo de Cultura Económica. Madrid, 1986. ISBN 84-375-0260-8)
• CARLES, Phillipe; CLERGEAT, André; COMOLLI, Jean-Louis: Dictionaire du jazz. Robert Laffont, París, 1988. ISBN 2-221-04516-5

• Paul Bley, en la emisión del 7 de nov. de 1988 del programa de La 2 (TVE) Jazz entre amigos.
  • Otra copia.
• Paul Bley con Lee Konitz, en la emisión del 4 de agosto de 1990 del mismo programa.