Malcolm Earl "Mal" Waldron was born on August 16, 1925 in New York City. His father worked for the Long Island Rail Road. Mal started taking classical piano lessons at age seven and, inspired by his love of jazz, also learned alto saxophone. He earned a B.A. in Music from Queens College, with the G.I. Bill (he'd been drafted in 1943 and served for two years, fortunately not seeing combat) paying for his tuition. He worked in jazz, blues, and R&B contexts and made his first recording in 1952 as a member of Ike Quebec's band. In '54-56 he was part of Charles Mingus's Jazz Workshop and recorded with Mingus. Waldron went out on his own as a leader at the end of 1956 with the album Mal/1 on Prestige and quickly became one of the prolific label's house pianists. The following year he added to his workload the position of Billie Holiday's accompanist, which garnered him more attention; he stayed in that position until her death in mid-'59.
There was a break in his career following a 1963 heroin overdose that caused a mental breakdown and left him with the shakes to the extent that he could not play the piano. There was temporary brain damage affecting his speed of thought, so even after he had re-taught himself how to play by listening to his own records, for a while he couldn't improvise. He compensated for this mental deficit, while it lasted, by writing out his solos in advance.