Після випуску дебютного альбому Black Sabbath повернулися до студії у червні 1970 року для запису наступного альбому. Робочою назвою платівки стала War Pigs(Воєнні свині), проте від нього довелося відмовитися, оскільки компанія звукозапису побоювалася негативної реакції в США. Проте антивоєнна спрямованість збереглася в оформленні альбому: її символізував спотворений фотографічний образ бородатої людини, що вискочила з-за дерева, зі щитом і мечем у руках[7].
Заголовна композиція альбому була написана прямо в студії за 25 хвилин.
У нас просто не вистачало матеріалу для нового альбому. Тоді Тоні просто почав грати Paranoid на гітарі. Нам знадобилося від 20 до 25 хвилин, щоби записати його
Загалом, як зазначали критики, другий альбом відрізнявся від першого більш загостреним звучанням, порівняно компактними аранжуваннями та меншою кількістю тривалих імпровізацій. Початкова реакція преси на нього (як і на всі ранні релізи групи) була переважно негативною. У ретроспективі альбом став вважатися класичним у своєму жанрі. Оглядач сайту Allmusic Стів Хьюї назвав Paranoid одним із найвпливовіших альбомів у жанрі хеві-метал:
Paranoid не тільки був найпопулярнішим із дисків Black Sabbath… він також є одним з найвеличніших і найвпливовіших альбомів усіх часів у жанрі хеві-метал. У цьому альбомі гурт відточив свій характерний саунд — оглушальні заупокійні композиції в мінорі, спочатку засновані на важкому блюз-року — і застосував до одноманітного набору пісень з рифами, що легко запам'ятовуються, більшість з яких зараз вважається історичною класикою хеві-метал.
В 2002 році альбом зайняв 3-ю позицію в рейтингу «100 найкращих рок-альбомів всіх часів» за версією журналу Classic Rock[11].
В 2011 році журнал Metal Hammer помістив в свій список ста найкращих кавер-версій п'ять пісень з альбому: «War Pigs» (Faith No More) — 26 місце, «Hand of Doom» (Slayer) — 55 місце, « Paranoid» (Megadeth) — 60 місце, «Electric Funeral» (Pantera) — 69 місце, і «Iron Man» (Вільям Шетнер) — 86 місце[12]