James W Red Holloway was born in Helena, Arkansas on May 31, 1927 to a mother who played piano and a father who played violin. At the age of five, he and his mother moved to Chicago, where he graduated from DuSable High School and attended the Conservatory of Music.
During grade school, Red played banjo and harmonica in school bands. His first musical instrument, a tenor sax, was given to him by his stepfather when he was twelve years old. During high school, he was in the DuSable big band, where he sat next to fellow classmate and reedman Johnny Griffin. By age sixteen, and while still in school, he was hired for his first professional engagement by bassist Gene Wright, who later went on to become a member of the Dave Brubeck Quartet. Red played with Wright's Big Band for three years at the Parkway Ballroom. When Red was nineteen, he joined the Army, where he became bandmaster for the U.S. Fifth Army Band.
After completing his military service, Red returned to Chicago and played with Yusef Lateef and Dexter Gordon, among others. In 1948 he was asked by blues vocalist Roosevelt Sykes to join Sykes' U.S. Road Tour. During this time, other bluesmen heard him and subsequently hired him, including Nat Lotsa Poppa Towles, Willie Dixon, Junior Parker, Bobby Blue Bland, Lloyd Price, John Mayall, and B.B. King. Because of these associations, Red became typecast, perhaps unfairly, as primarily a blues player.