Born in New York City, Waldron's jazz work was chiefly in the hard bop, post-bop and free jazz genres. He is known for his distinctive chord voicings and adaptable style, which was originally inspired by the playing of Thelonious Monk.
After obtaining a B.A. in music from Queen's College, New York, he worked in New York City in the early 1950s with Ike Quebec, Big Nick Nicholas, and rhythm and blues groups. He worked frequently with Charles Mingus from 1954 to 1956 and was Billie Holiday's regular accompanist from 1957 until her death in 1959. He also supervised recording sessions for Prestige Records, for which he provided arrangements and compositions (including the jazz standard Soul Eyes). After Holiday's death he chiefly led his own groups.
Waldron had a unique playing style. He played chords in a lower bass part of the keyboard, and is comparable to Bud Powell in his dissonant voices. His solo style is in noted contrast to players like Red Garland.
He was frequently recorded, both as a leader and sideman, with, among others, John Coltrane, Eric Dolphy, Clifford Jordan, Booker Little, Steve Lacy, Jackie McLean and Archie Shepp.
Besides performing he composed for films (The Cool World, Three Bedrooms In Manhattan and Sweet Love Bitter), theatre, and ballet. In 1963 he had a major nervous breakdown, and had to re-learn his skills, apparently by listening to his own records. Waldron's playing style re- emerged more brooding, starker and percussive, combining bebop and avant-garde melodies, and at times weaving repetitive melodic motifs using just a few notes over a drone like accompaniment figure. After working on a film score in Europe he moved there permanently in 1965 initially living in Munich, Germany and in his last years he was based in Brussels, Belgium. On the principle that working at local venues reduced his fee, he avoided playing in the city in which he lived. He regularly returned to the United States for bookings.