Bryant was born in Huntington, West Virginia, and grew up in Columbus, Ohio, becoming a fixture of the local jazz scene. He worked with Tiny Grimes and Stomp Gordon before founding his own ensemble, the Carolyn Club Band, in 1951. He signed with Dot Records in 1954 and released several albums as a leader in the second half of the 1950s. In 1952, his live recording All Nite Long (a faster version of Night Train) became a hit R&B single in the U.S.
Bryant's contract with Dot ended in 1957, and he returned to Columbus to do mostly local engagements, playing often with pianist-organist Hank Marr. Nancy Wilson also sang in his group. It wasn't until his appearance on the 1968 Groove Holmes album That Healin' Feelin' that he resurfaced beyond regional acclaim, and soon after he began leading dates for Prestige Records. He recorded extensively for the label from 1969 through the middle of the 1970s, being a sideman with Ivan Boogaloo Joe Jones, Johnny Hammond Smith, Charles Kynard, and Sonny Phillips; his 1970 release Soul Liberation was his most commercially successful, reaching No. 35 on the U.S. Black Albums chart and No. 15 on the Top Jazz Albums chart. Bryant continued to record into the early 1980s, then returned to mostly local dates in Columbus. He died there in 1991.
Rusty Bryant was the father of Eric Royal Bryant and pop singer Stevie Woods, the latter having a moderately successful recording career in the early 1980s with the top 40 hit songs Steal the Night and Just Can't Win 'Em All. Rusty was the grandfather of Tiana Woods, an L.A. based singer/songwriter and front woman for the band Living Eulogy.