Main Index Pablo Honey The Bends OK Computer Kid A Amnesiac Hail to the Thief In Rainbows The King of Limbs A Moon Shaped Pool Thom Yorke Jonny Greenwood Ed O'Brien Colin Greenwood Philip Selway
In spring 2002, 'Where Bluebirds Fly' was created during the rehearsals, though elements of it might have been programmed by Thom before that, a rough version of the song was possibly included on his three demo CDs. Colin mentioned that this track was something Thom did on his laptop.
In 2003, a couple of samples, that come from the elements used to construct the electronic backing track, were made available in the Loophole section of radiohead.com. Their titles were 'R114', 'R115', 'R116' and 'R148':

Since July 2002, the song was used as the intro music for Radiohead concerts, and as it was finished by this point already, you could hear the vocal coming in just as the track was faded out on many shows.
Colin: "It was some music that Thom did on his laptop, I think. And every time you hear it our hearts quickened, because we had it as our coming on music for a year and a half."
On May 26th 2003, the song was released as a b-side on the There There single, where Graeme Stewart, who recorded and engineered the rehearsals, is not credited for engineering. He is mentioned on the Japanese compilation Com Lag, though, suggesting they simply forgot to mention him on the single.
On March 27th and 28th 2005, 'Where Bluebirds Fly' an orchestral arrangement played at the Ether Festival. Thom sang the melody wordless, and was joined by Lubna Salame. The two singers were accompanied by the London Sinfonietta (including six Ondes Martenots played by Valerie Hartmann-Claverie, Bruno Perrault, Nathalie Forget, Fabienne Martin-Besnard, Nadia Ratsimandresy and Pascale Rousse-Lacordaire) conducted by Martyn Brabbins with the Arab Orchestra of Nazareth.
This video was edited from three sources for this website and is coupled with a recording that was aired by the BBC and comes from the first night on March 27th 2005: