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.