As a teenager Gaines played in brass bands in Philadelphia. Gaines moved to New York City in 1920, where he joined the orchestra of Wilbur Sweatman. He soon signed on with Clarence Williams's house band, then played with Sam Wooding, Earl Walton, Leroy Smith, Fats Waller, Charlie Johnson, and the Hot Chocolates.
In the 1930s Gaines launched his own band in Philadelphia; he recorded occasionally, including once with Williams in 1934. Concomitantly he continued playing with Smith and also played in Louis Armstrong's orchestra. He continued to lead bands in Philadelphia into the 1950s, especially at the jazz venue Carroll's. In the 1960s he played in a trio at the Hangover Club. Gaines went into retirement in the 1970s.
- Barry Kernfeld, ed. (2002). "Gaines, Charlie". The new Grove dictionary of jazz, vol. 2 (2nd ed.). New York: Grove's Dictionaries Inc. p. 3. ISBN 1561592846.
- Nicholson, Jim (November 26, 1986). Phila. Musician Charlie Gaines, Played Trumpet With Jazz Greats. Philadelphia Inquirer