Aunque nacido en Pittsburgh, Paul creció en Detroit, donde pronto formó parte de los círculos de jazz. Se trasladó a Nueva York, donde tocó en el quinteto de J.J.Johnson y Kai Winding. En 1955 -con 20 años- se incorporó al primero de los quintetos legendarios de Miles Davis, con el que permaneció hasta 1963 y grabó los álbumes 'Cookin'' (1957), 'Relaxin'' (1958), 'Workin'' (1959) y 'Steamin'' (1961).
En los años sesenta formó un trío con Wynton Kelly y Jimmy Cobb y trabajó como músico de sesión con diversos artistas como Wes Montgomery, Tony Scott y Barry Harris. Chambers, con la salud deteriorada por un excesivo consumo de drogas, murió de tuberculosis en enero de 1969 a los 33 años.