Holloway was born to Condredge Holloway, Sr., and Dorothy Holloway. Condredge's grandfather on his father's side was born a slave, but was emancipated as a child in 1865. Dorothy was hired to work at the Marshall Space Flight Center in Huntsville in 1962, becoming the first African American employee of NASA.
Surprisingly, football wasn't Holloway's favorite sport; he preferred baseball. After starring as a high school player at Lee High School in Huntsville, he was drafted as a shortstop by the Montreal Expos in 1971. Holloway was Montreal's first pick, and he was the fourth player selected overall. However, Holloway's mother, insisting her son attend college, refused to sign the contract (Condredge was 17, too young to sign a contract under Alabama law) and instead he went to Tennessee. In so doing Holloway became the first African-American to start at the quarterback position in a Southeastern Conference school. In addition to being the first black quarterback at Tennessee and in the Southeastern Conference, Holloway also was the first black baseball player in Tennessee history. The outstanding prospect bypassed a baseball career, and Holloway opted instead, for a two-sport collegiate career and went on to excel on the diamond. He garnered All-SEC and All-America honors as a shortstop in 1975 and finished with a .353 career batting average. Holloway — still the owner of Tennessee's longest hitting streak at 27 games — was selected to Tennessee's All-Century Baseball Team, making him the only Tennessee student-athlete named to all-century squads in both baseball and football.
In his three seasons (1972–74) as a starter, Holloway directed the Vols to the 1972 Astro-Bluebonnet, 1973 Gator, and 1974 Liberty Bowls and an overall record of 25-9-2. He ended his career with the best interception-to-attempt ratio in Tennessee history, throwing just 12 interceptions in 407 collegiate attempts. During his three seasons, he completed 238 of 407 passes for 3,102 yards and 18 touchdowns, and rushed 351 times for 966 yards and nine touchdowns.