Hargrove was born in Dallas, Texas, and was discovered as a potential jazz talent when Wynton Marsalis visited his high school. One of his biggest influences was saxophone player David "Fathead" Newman, who played with the Ray Charles Band at Hargrove's junior high school. Hargrove spent one year (1988–1989) studying at Boston's Berklee School of Music, but could more often be found in New York City jam sessions, and finally transferred to New York’s New School. His first recording in New York was with the saxophonist Bobby Watson. Shortly afterwards he made a recording with Superblue featuring Watson, Mulgrew Miller, and Kenny Washington. In 1990 he released his first solo album, Diamond in the Rough, on the Novus/RCA label, along with four other albums.

He signed a recording contract with Verve Records, which gave him the opportunity to record with some of the major jazz musicians on With the Tenors of Our Time, including Joe Henderson, Stanley Turrentine, Johnny Griffin, Joshua Redman, and Branford Marsalis. In 1993 he was commissioned by the Lincoln Center Jazz Orchestra, and wrote The Love Suite: In Mahogany. Hargrove won a Grammy Award in 1998 for the album Habana with his Afro-Cuban band, Crisol.

Hargrove has recorded with a wide range of musicians, including: Sonny Rollins, Michael Brecker, Jackie McLean, Slide Hampton, Natalie Cole, Diana Krall, Abbey Lincoln, Diana Ross, Steve Tyrell, Kenny Rankin, John Mayer, Rhian Benson, Carmen McRae, Shirley Horn, Jimmy Smith, Danny Gatton, Method Man, Common, Erykah Badu, D'Angelo, and Gilles Peterson.

Hargrove is the leader of the progressive group The RH Factor, which combines elements of jazz, funk, hip hop, soul, and gospel music.