In an effort to capitalise on the recent UK chart success of their eponymous debut album, Black Sabbath returned to the studio with producer Rodger Bain in June 1970, just four months after the album was released. Paranoid was recorded at Regent Sound Studios and Island Studios in London, England.
The album's title track was written as an afterthought. As drummer Bill Ward explains: "We didn't have enough songs for the album, and Tony (Iommi) just played the guitar lick and that was it. It took twenty, twenty-five minutes from top to bottom." In the liner notes to the 1998 live album Reunion, bassist Geezer Butler recounts to Phil Alexander that they wrote the song "in five minutes, then I sat down and wrote the lyrics as quickly as I could. It was all done in about two hours." According to Alexander, "Paranoid" "crystallized the band's writing process, with Iommi initiating the ideas with his charred riffs, Ozzy (Osbourne) working on a melody, Geezer providing drive and the majority of the lyrics, and Bill Ward locking into a set of often pounding rhythms beneath Butler's bass rumble." The single was released in September 1970 and reached number four on the UK charts, remaining Black Sabbath's only top ten hit.
Most of the songs on Paranoid evolved during onstage improvisational jams. In the Classic Albums documentary on the making of Paranoid, guitarist Tony Iommi recalls that "War Pigs" came from "one of the clubs" with Butler adding, "During the song "Warning" we used to jam that out and that particular night when we were jamming it out Tony just went da-dum!" In the same documentary, Iommi demonstrates his approach to the guitar solo in the song, explaining that "I always tried to keep the bottom string ringing so it fills it out nicely." On "Planet Caravan", Osbourne sings through a Leslie speaker, with the singer telling Mojo in 2010, "Then Rodger Bain used an oscillator on it – whatever that is. It looks like a fridge with a knob on."