Born in Cleveland, Bailey studied at the Cleveland Conservatory of Music. In 1947, he joined Dizzy Gillespie's group; a year later, he began playing with Hampton's big band.
In 1953, during a tour of Europe, Bailey left the group and settled in Sweden. He spent most of the rest of his career in Europe, playing with Harry Arnold's big band in Sweden and with the Paris Reunion Band. He also recorded with Quincy Jones, Les McCann, and Stan Getz.
According to Ren_ van Beek, a Dutch jazz impresario, Bailey toured actively in Europe up until his death. "I had a gig scheduled with him in two weeks," van Beek said. "He was still in great condition."