He was born in Tulsa, Oklahoma, the son of Eula and Frank Haynes. He served in the US Air Force Band between 1947 and 1950, and after his discharge lived in Oakland, California with his first wife and children. During the 1950s, he played in various jazz groups in clubs in San Francisco, before forming his own quartet who toured in California. He first recorded in Los Angeles in 1954, as a member of the Gerald Wilson big band.
Haynes remarried and moved to New York City in 1959. Over the next few years, he appeared at many jazz clubs in New York, including Birdland, the Five Spot, the Village Vanguard, and the Village Gate. In 1961, he was a member of the Dave Bailey Quintet who recorded the albums Reaching Out, Bash!, and 2 Feet in the Gutter, which included the original version of the popular tune "Comin' Home Baby". He also recorded with Kenny Dorham, Les McCann, Walter Bishop, T-Bone Walker, Sonny Forriest, Grant Green and Randy Weston. Haynes recorded his own album, Frankly Speaking, with guitarist and songwriter Rudy Stevenson, but it was never released.
With Dave Bailey
- 2 Feet in the Gutter (Epic, 1961)
- Bash! (Jazz Line, 1961)
- Reaching Out (Jazztime, 1961)
- Modern Mainstream (Fontana, 1963)
- Walter Bishop Jr., Bish Bash (Xanadu, 1977)
- Tommy Flanagan, Tommy Flanagan Trio and Sextet (Onyx, 1973)
- Grant Green, Green Blues (Muse, 1973)
- Sonny Forriest, Tuff Pickin (Decca, 1966)
- Les McCann, Les McCann Ltd. in New York (Pacific Jazz, 1962)
- Randy Weston, Blues (Trip, 1974)
- Gerald Wilson, Big Band Modern (Jazz Factory, 2006)
- Jan Evensmo, The tenor sax of Frank Haynes, 2013. Retrieved 20 February 2014
- "The Dave Bailey Quintet - 2 Feet In The Gutter". JAZZDISCO.org. Retrieved 2013-10-09.
- Frank Haynes at Allmusic.com. Retrieved 21 February 2014
- Lewis Porter (ed.), The John Coltrane Reference, Routledge, 2013, p.334