Né à Montréal en 1932, Paul Bley avait cofondé le Montreal Jazz Workshop à 17 ans.
À 20 ans, il jouait avec Charlie Parker et lançait son premier disque en tant que soliste, Introducing Paul Bley. Charles Mingus et Art Blakey l'accompagnaient alors.
Dès les années 40, il entamait donc une brillante carrière qui s'est étendue sur huit décennies.
Paul Bley fut l'un des premiers à reconnaître l'importance musicale d'Ornette Coleman, pionnier du free jazz. Les deux musiciens - accompagnés de Don Cherry, de Charlie Haden et de Billy Higgins - ont joué au Hillcrest Club de Los Angeles en 1958. Ces prestations sont devenues légendaires et sont immortalisées sur l'album Live at the Hillcrest Club 1958.
Celui qui fut de 1957 à 1964, l'époux d'une autre pianiste de renom, Carla Bley, avait aussi pleinement adhéré au mouvement free dans la seconde moitié des années 50.
En 1961, le pianiste Paul Bley devenait membre du groupe de jazz de chambre d'avant-garde Jimmy Giuffre Trio. Open, to Love, lancé en 1972, fut son premier véritable disque solo.
Au cours des années 80, Paul Bley a collaboré avec les musiciens John Surman, Bill Frisell, Paul Motian, Gary Peacock, Tony Oxley, Evan Parker et Barre Phillips. Il a également fait de nombreuses tournées durant cette décennie.
Il fut aussi l'un des premiers à aborder la musique électronique. Il a réussi à imposer sa science de l'improvisation, son art du silence, la subtilité de son jeu dépouillé auprès des plus grands: Sonny Rollins, Coleman Hawkins, Chet Baker... Mais aussi à la tête de nombreux trios, un art qu'il maitrisait parfaitement à l'égal de Bill Evans.
Depuis les années 70, Paul Bley était devenu l'un des musiciens fétiche de la prestigieuse maison de disques allemande ECM Records, signant une vingtaine d'albums, dont "Not two, not one". Le musicien avait publié en 199 son autobiographie: "Paul Bley and the transformation of jazz". Sa dernière apparition au Festival international de jazz de Montréal remonte au 3 juillet 2003. Il avait joué la dernière fois en France en septembre 2010 à la Cité de la Musique à Paris.