Malone was born in Honolulu, Hawaii. His father, Odie Malone, was a U.S. Navy pilot who survived the Japanese attack on Pearl Harbor. Malone graduated from North Texas State University with Lou Marini, who would also become a member of the Blues Brothers band. Both were members of the One O'Clock Lab Band at North Texas.
After graduation, Malone worked in bands of Woody Herman (1969), Duke Pearson (1970), Louie Bellson (1971), Doc Severinsen, Frank Zappa (1972),[2] and Blood, Sweat & Tears (1973).[2] In 1973, Malone began a close, fifteen-year association with Gil Evans, whom he has called a mentor.[2] He recorded albums with Evans and toured Europe, Japan, and the Far East. In 1975 Malone toured with Billy Cobham and in 1976 with the Band. He also contributed to the band Blood, Sweat & Tears on their albums 3 and 4.
After he was heard performing with Ten Wheel Drive and Genya Ravan, he received a call from Saturday Night Live a late-night comedy television program. From 1975 to 1985 he worked as arranger for Saturday Night Live[1] and from 1981 to 1985 as musical director. He wrote the chart for the skit that introduced John Belushi and Dan Aykroyd as the Blues Brothers. He appeared in the movie version and in 1993 reunited with Paul Shaffer, who worked for Saturday Night Live, and Will Lee, who was a member of the CBS Orchestra. He worked on the film score for Blues Brothers 2000. He joined the CBS Orchestra on November 1, 1993, and contributed more than 1,600 arrangements to the Late Show with David Letterman.
As a studio musician, he has been heard on more than 1,000 records, more than 3000 radio and television commercials, and over 4,000 live television shows. He has played themes for CBS This Morning, Murder, She Wrote, and the 1992 Winter Olympics. His solo album, Soul Bones, includes guest appearances by Paul Shaffer and John Popper of Blues Traveler. Additional film credits include The Last Waltz and Sister Act.
In 2007 Malone was invited by music director Geoffrey Moull to arrange and perform a concert with the Thunder Bay Symphony Orchestra. In 2011 Malone was guest artist with the University of Southern Mississippi Symphony Orchestra.