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, Bob Monkhouse and Kathy Kirby, and on television programs such as 'Opportunity Knocks'. Bailey was also part of a Sheffield based trio founded in 1963 with Tony Oxley and Gavin Bryars called 'Joseph Holbrooke' (named after the composer, whose work they never actually played). Although originally performing relatively 'conventional' jazz this group became increasingly free in direction.
Bailey moved to London in 1966, frequenting the Little Theatre Club run by drummer John Stevens. Here he met many other like-minded musicians, such as saxophonist Evan Parker, trumpet player Kenny Wheeler and double bass player Dave Holland. These players often collaborated under the umbrella name of the Spontaneous Music Ensemble, recording the seminal album Karyobin for Island Records in 1968. In this year Bailey also formed the Music Improvisation Company with Parker, percussionist Jamie Muir and Hugh Davies on homemade electronics, a project that continued until 1971. He was also a member of the Jazz Composers Orchestra and Iskra 1903, a trio with double bass player Barry Guy and trombone player Paul Rutherford that was named after a newspaper published by the Russian revolutionary Vladimir Lenin.
In 1970, Bailey founded the record label Incus with Tony Oxley, Evan Parker and Michael Walters. It proved influential as the first musician-owned independent label in the UK. Oxley and Walters left early on; Parker and Bailey continued as co-directors until the mid-1980s, when friction between the men led to Parker's departure. Bailey continued the label with his partner Karen Brookman until his death in 2005.
Along with a number of other musicians, Bailey was a co-founder of Musics magazine in 1975. This was described as "an impromental experivisation arts magazine" and circulated through a network of like-minded record shops, arguably becoming one of the most significant jazz publications of the second half of the 1970s, and instrumental in the foundation of the London Musicians Collective.
1976 saw Bailey form Company, an ever changing collection of like-minded improvisors, which at various times has included Anthony Braxton, Tristan Honsinger, Misha Mengelberg, Lol Coxhill, Fred Frith, Steve Beresford, Steve Lacy, Johnny Dyani, Leo Smith, Han Bennink, Eugene Chadbourne, Henry Kaiser, John Zorn, Buckethead and many others. Company Week, an annual week long free improvisational festival organised by Bailey, ran until 1994.