According to Radiohead bassist Colin Greenwood, Thom Yorke wrote 'Creep' while studying at Exeter University in the late 1980s. Guitarist Jonny Greenwood said the song was inspired by a girl that Yorke had followed around who showed up unexpectedly during a show by the band.

In 1992 during rehearsal sessions with producers Sean Slade and Paul Q. Kolderie, Radiohead spontaneously performed 'Creep'. Yorke described 'Creep' to the producers as 'our Scott Walker song'; Slade and Kolderie mistook the singer's remark and believed the song was a cover. After tension arose due to unsatisfactory attempts at recording other songs, Slade and Kolderie tried to improve morale by requesting Radiohead to play 'Creep' again. The band recorded the song in a single take; after the performance everyone in the room burst into applause. Once the band assured Kolderie that 'Creep' was an original song, he called EMI to tell them to consider the song as Radiohead's next single.

While the recording had minimal overdubs and the band did not intend to release it, the producers were impressed with the song. Due to similarities to 'The Air That I Breathe', a song recorded by The Hollies in 1973, Albert Hammond and Mike Hazlewood are credited as co-writers of 'Creep'.