Malone nació en Albany, Georgia. Comenzó a interesarse por la música con cuatro años, aprendiendo a tocar una guitarra de juguete que su madre le había regalado. Sus primeras influencias fueron B.B. King y The Dixie Hummingbirds.[3] Con un aprendizaje mayormente autodidacta, Malone quedó impactado a los doce años por una actuación en televisión de George Benson con Benny Goodman.[4][5]
Comenzó su andadura musical en 1988, primero con Jimmy Smith, con quien colaboró durante dos años y después con Harry Connick Jr. con quien permaneció los siguientes tres años. En 1995 entró a formar parte como guitarrista del trío de acompañamiento de Diana Krall,[4] participando en la grabación de tres álbumes nominados a los Premios Grammy, incluyendo When I Look in Your Eyes, álbum ganador del Grammy a la mejor interpretación vocal de jazz. A finales de la década, Malone participó en varias grabaciones del pianista Benny Green: Kaleidoscope (1997), These Are Soulful Days (1999) y Naturally (2000). Posteriormente, ambos formaron un dúo con el que publicaron los álbumes Jazz at The Bistro en 2003 y Bluebird en 2004. Estuvieron realizando actuaciones hasta 2007.
Malone ha colaborado en giras con Ron Carter, Roy Hargrove y Dianne Reeves y ha formado parte como músico de sesión del acompañamiento de artistas como Kenny Barron, Branford Marsalis, Wynton Marsalis, Jack McDuff, Mulgrew Miller y Eddie "Cleanhead" Vinson. Grabó su primer álbum en solitario en 1992 y dirigió además su propio trío y cuarteto. Otras destacadas colaboraciones has sido con Bobby Hutcherson, Dr. Lonnie Smith y con el veterano pianista Hank Jones durante la celebración de su 90 cumpleaños. En octubre de 2008 formó pareja con el guitarrista Bill Frisell. Durante el año siguiente, Malone se integró en la banda del saxofonista Sonny Rollins.
Malone realizó una grabación en directo entre los días 9 y 11 de septiembre de 2005, en el Jazz Standard de Nueva York, que fue publicada por el sello Maxjazz en dos álbumes, Live at Jazz Standard, Volume One (2006) y Live at Jazz Standard, Volume Two (2007). La banda que grabó estos álbumes, bajo el nombre de The Russell Malone Quartet, estuvo formada por el pianista Martin Bejerano, el bajista Tassili Bond y el batería Johnathan Blake.
En 2010 publicó Triple Play (también con Maxjazz) con David Wong al bajo y Montez Coleman a la batería. En su álbum, All About Melody contó con la colaboración del pianista Rick Germanson, el bajista Luke Sellick y el batería Willie Jones III.[6][7]
