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 Music Video
The title phrase '15 Step', along with a reference to 'A Rat's Nest', can be seen in this sketch from the 'scrapbook' section of radiohead.com:

baudolino
This early draft of lyrics for 'A Punch-up At A Wedding' was added by Thom at the bottom of a lyric sheet that also featured the finished lyrics of that song. A line, that would later end up in '15 Step', is also included. He used this sheet during the summer 2002 shows in Spain and Portugal, apparently he couldn't remember all the lyrics yet. At some point, this piece of paper was fortunately thrown into the audience:


go ahead the stage is yours.
if you think you can do better
you used to be alright, what-happened?
keep moving or you r dead. keep moving or you r dead.
how i wish you'd stay out of my face.
there's always someone spoils the party
just you wait till your chained down
worried and unhinged
you have really gone and done it now
just a trick to make you stupid
all these sad heroics
let me tell you how it really is
we are here to spoil your party
empty vessels make the most noise
survival of the fittest
wading through the marshes
hypocrits, opportunists,
userers flatterers and thiefs.
im sick of all your bullshit.
im sick of all these fucking mindgames.
who invited you anyway?
A few related lines appeared in the 'scrapbook' section of radiohead.com:

15a
15b
lake1
lake2
'15 Step Thing' was one of the titles that appeared on the blackboard the band used during two weeks of rehearsals from september 19th to 30th 2005. At the end of that session, Colin posted a picture of this board on Dead Air Space on september 30th, unfortunately (and probably intentionally) in rather low resolution, so that some of it can't be deciphered:
On february 20th 2006, the band posted this picture of early handwritten lyrics on Dead Air Space (click image for full size):

lyrics
On march 8th 2006, shortly after sessions with Mark Stent had come to an unfruitful end, another photo of a blackboard (and a perhaps slightly worried Ed) was posted on Dead Air Space. A tour had been scheduled for may and june to escape the frustration of the recent sessions and to breathe new life into the project. Rehearsals for the upcoming dates had begun recently, and this board shows which new songs were at this point considered for inclusion in the setlists. '15 Step' was one of these, and would indeed be played (click image for full size):
On march 8th 2006, along with the photo of the Tour blackboard, this image was also posted on Dead Air Space. The name of the image indicates Thom is working on '15 Step':

thom
On december 18th 2006, a line from the lyrics appeared on the start page of radiohead.com. This happened shortly after the sessions at Nigel's Covent Garden studio had ended and the band had begun a Christmas break:

headline
The final version of the song is essentially a live recording the band had made right after the Christmas break in early January.
On january 11th 2007, Plank posted a picture of a mellotron on his blog on stringsreunited.com. This instrument was used during the recording of the song:

click to enlarge the image on the right
On february 3rd 2007, Thom posted these lines on Dead Air Space:

post
On april 17th 2007, a sample from the studio recording was made available in the Hodiau Direkton section of radiohead.com:
On may 9th 2007, another sample of Thom repeating "etcetera etcetera" appeared in the Hodiau Direkton section of radiohead.com:
On may 26th 2007, a phrase from the lyrics appeared on the start page of radiohead.com:

start page
On may 31st 2007, a picture of an etching by Stanley that makes use of a handwritten lyric sheet appeared in the Hodiau Direkton section of radiohead.com. The verse with the lines about "a dark voice sitting on the staircase" had been unknown up to this point:

etching
On september 3rd 2007, Plank posted a picture of an Autoharp on his blog on stringsreunited.com. Ed had used that instrument in the song's second half:

autoharp
For the webcast on november 9th 2007, a special '15 Step' clip was made by Adam Buxton and Garth Jennings. The clip used the climax of the movie SE7EN by David Fincher:
This photo shows Jonny's Max/MSP patch for '15 Step', it was taken on january 16th 2008 at Rough Trade East in London, before the gig was moved to 93 Feet East:

Max/MSP patch
On february 8th 2009, Jonny and Thom performed the song at the Grammy award show as the band had been nominated for the 'Album of the Year' award for In Rainbows. For this occasion a special brass arrangement of '15 Step' was created by the USC Trojan Marching Band who would perform the song with Thom and Jonny:
In december 2009, a recording from the february 6th 2009 rehearsal at Sony Studios’ Stage 25 was released by the USC Trojan Marching Band on the 2 CD compilation Trojan Legacy: 40 Years of Dr. Arthur C. Bartner and The Spirit of Troy:
Live performances #100 to #123 during the touring for The King of Limbs:
100. june 28th 2011 Glastonbury Festival Pilton UK Link
  The King of Limbs tour (1st half) 09/'11 02/'12 march 2012 april 2012 05/'12 june 2012
15 Step [23] 28 29 03 05 09 11 15 09 11 12 14 17 18 21 29 31 01 03 05 06 08 10 13
Weird Fishes/Arpeggi [23] 28 29 27 29 01 03 05 06 07 09 11 13 15 09 12 14 18 21 29 31 06 08 10
All I Need [6] 28 29 29 03 11 15
Videotape [1] 09
Live performances #124 to #144 during the touring for The King of Limbs:
  The King of Limbs tour (2nd half) july 2012 september 2012 october 2012 november 2012
15 Step [21] 10 11 13 15 25 27 29 20 22 23 25 30 08 14 15 16 18 09 12 13 16
Weird Fishes/Arpeggi [20] 10 15 27 29 20 22 23 26 29 06 08 09 12 15 16 18 06 12 13 17
Videotape [7] 10 29 09 12 16 12 16
  2016 A Moon Shaped Pool tour may 2016 06/2016 july 2016 august 2016 sept./oct. 2016
15 Step [1] 26
Weird Fishes/Arpeggi [17] 20 23 27 01 03 17 02 27 29 31 04 06 20 11 30 03 07
All I Need [4] 21 03 04 07
Videotape [1] 20
  2017 A Moon Shaped Pool tour march/april 2017 june 2017 july 2017
15 Step [23] 05 08 09 11 14 17 18 21 06 07 09 11 14 16 18 20 23 28 30 02 04 07 19
Weird Fishes/Arpeggi [17] 30 05 09 14 18 06 09 11 14 16 23 28 30 02 04 07 19
All I Need [19] 30 01 05 09 11 17 21 06 07 11 16 18 20 28 30 02 04 07 19
Videotape [5] 30 03 18 07 02