Bailey was born in Sheffield, England. A third generation musician, he began playing the guitar at the age of ten, going on to study with John Duarte among others. As an adult he found work as a guitarist and session musician in clubs, radio, dance hall bands, and so on, playing with many performers including Gracie Fields. Bailey later began to play in a trio in Sheffield with Tony Oxley and Gavin Bryars called Joseph Holbrooke. Although originally performing relatively 'conventional' jazz this group became increasingly free in direction.
Bailey moved to London in 1966, where he met many like-minded musicians, such as saxophonist Evan Parker, trumpet player Kenny Wheeler, drummer John Stevens, and double bass players Barry Guy and Dave Holland, occasionally collaborating under the umbrella name of the Spontaneous Music Ensemble (SME). This group recorded the seminal album Karyobin for Island Records in 1968. In this year Bailey also formed the Music Improvisation Company with Parker, percussionist Jamie Muir, Hugh Davis on organ and Holland, a project that continued until 1971.
In 1970, Bailey founded the record label Incus with Tony Oxley and Evan Parker, often said to be the first independent label owned by musicians.