Después, trabajó con Brenda Lee y con la Tommy Dorsey Orchestra, mientras realiza sus estudios universitarios.

En 1973 es llamado por su compañero Lou Marini para sustituir a Chuck Winfield en la banda de jazz-rock Blood, Sweat & Tears, con los que permanece sólo un año, grabando un disco (No sweat).

Mantendrá después una larga relación con Gil Evans (1973-1985), aunque lo simultanea con Frank Zappa (1976) y con las bandas de la NBC y de Saturday Night Live, para la televisión.

En 1980, este espectáculo se convierte en película paródica, dirigida por John Landis, con el nombre de The Blues Brothers, que será en adelante el nombre de la propia banda.

En 1993, paralelamente, Malone se integra en la Orquesta de la CBS, con quien permanecerá largo tiempo, a la vez que realiza colaboraciones y discos como líder (Soul Bones).