In composing 'Paranoid Android', Radiohead fused together parts from three different songs, each of which had been written by a different member of the band. The idea to combine the pieces into a single track was inspired in part by the format and structure of 'The Beatles - Happiness Is a Warm Gun'.

Colin Greenwood admitted that the band, in attempting it to see if they could make the disparate elements work together, 'felt like irresponsible schoolboys who were doing this ... naughty thing, cause nobody does a six-and-a-half-minute song with all these changes. Its ridiculous'. The song was at first intended to be humorous, and took its title from Marvin the Paranoid Android from 'Douglas Adams - The Hitchhiker's Guide to the Galaxy' series of books. Yorke has said the title 'was chosen as a joke. It was like, 'Oh, I'm so depressed'. And I just thought, that's great. That's how people would like me to be. And that was the end of writing about anything personal in the song. The rest of the song is not personal at all'.

In an early interview, Colin Greenwood described it 'just a joke, a laugh, getting wasted together over a couple of evenings and putting some different pieces together'. The band used Queen's 'Bohemian Rhapsody' and the work of the Pixies as reference points while writing; yet Ed O'Brien denies they wrote 'a 'Bohemian Rhapsody' for the nineties', while Jonny Greenwood considers it too tense and simple to rival Queen's song.

'Paranoid Android' was recorded in actress Jane Seymour's 15th century mansion (which Yorke was convinced was haunted) near the village of St Catherine, near Bath, Somerset. The first edit was over 14 minutes long and included a long organ interlude performed by Jonny Greenwood. Radiohead played this extended version during a tour with Alanis Morissette in September 1996. O'Brien said 'when we started playing it live, it was completely hilarious. There was a rave down section and a Hammond organ outro, and we'd be pissing ourselves while we played. We'd bring out the glockenspiel and it would be really, really funny'.

Before the song's first live performance, Yorke told audiences that 'if you can have sex to this one, you're fucking weird.' He also sarcastically referred to the version of the song played during the tour as 'a Pink Floyd cover'. Radiohead were inspired by the editing of 'The Beatles - Magical Mystery Tour' (described by Colin Greenwood as 'brutal'), to shorten the song to a final six and a half minutes, a process that led to Jonny Greenwood's organ section being replaced by a substantially shorter guitar fade out. However, it took the band a year and a half to learn how to play the final version in live performance.