Die 1990er Jahre

1994 wurde die Band in Hamm (Wiescherhöfen) von Hendrik Spließ, Thorsten Grams, Daniel „Zwiebel“ Jacobs und Jörg H. gegründet. In der Anfangszeit nannten sie sich „The Pain“, traten aber nie unter diesen Namen auf. 1996 erschien das erste Demotape (1996) unter den Bandnamen Paranoya, welches in der lokalen Punkszene wohlwollend aufgenommen wurde. Während der Aufnahme hierzu verließ Jörg H. die Band, so dass die ersten Auftritte in Jugendzentren der Umgebung von Hamm ohne Bassisten stattfanden. Im Herbst 1996 kam dann Lars W. als neuer Bassist zur Band.

1997 folgte das zweite Demotape (Manipulation). Aufgrund dieses Tapes, welches auch außerhalb von Nordrhein-Westfalen auf überwiegend positive Resonanz stieß, konnte die Band im Vorprogramm von Bash und Popperklopper spielen und trat ebenfalls bei einem Geheimauftritt der englischen Punkbands Contempt und Sick on the Bus im Vorprogramm auf.

1998 folgte das nächste Demotape (Paranoya), welches der Band weitere Auftritte mit bekannten Szenebands wie 1. Mai 87, The Vageenas und Pestpocken verschaffte. Aufgrund des Geheimauftritts spielte Paranoya im Vorprogramm der Band Substandard aus England im autonomen Zentrum Mülheim. Im gleichen Jahr erschien auf Harmonyrec. ein Vinylsampler (Wohlstandsneurose) mit Recharge, Sick on the Bus, Contempt, Dekadenz und anderen, dessen Erlös Obdachloseneinrichtungen gespendet wurde. Als eine der wenigen Bands ohne Plattenvertrag war Paranoya dort mit zwei Liedern vertreten. Dieser Sampler wurde nicht nur in Deutschland, sondern europaweit, in der D.I.Y.-Punkszene vertrieben.

Es folgte das erste offizielle Release einer 7"-Vinyl-EP (Out) mit 5 Stücken vom Demo (Paranoya) bei Na Und?! Records. Die EP erschien in einer Auflage von 500 Exemplaren und schaffte es sogar über den Atlantik, wo sie in den USA bei Maximumrocknroll reviewed wurde:

Weitere Auftritte mit Rasta Knast, District, Bad News usw. folgten und steigerten den Bekanntheitsgrad der Band innerhalb der D.I.Y.-Punkszene. 1999 erschien bei Na Und?! Records der 7"-Vinyl-Sampler Human Dust Vol. 1, auf dem Paranoya mit Not Enough, Mass Murders und Antidote vertreten waren. Bei Unbedeutend, das ebenfalls von Paranoya veröffentlicht wurde, singt der Schlagzeuger Thorsten Grams (zu diesem Zeitpunkt auch Sänger bei Cuatro X), während die anderen die Backing Vocals übernahmen.

2000 bis 2010

Im Juli 2000 begab sich die Band ins Studio, um neues Material einzuspielen. Durch die gespielten Konzerte im Frühjahr 2000 mit Not Enough und den Krombacher Kellerkinder, welche ihre Alben auf Horror Business Records veröffentlichten, wurde das Label auf die Band aufmerksam. Man vereinbarte eine Kooperation mit Na Und?! Records, zum Release eines Albums auf CD und Vinyl. Die CD sollte bei Horror Business Records erscheinen und die Vinyl-Version bei Na Und?! Records. Jedoch sprang Na Und?! Records ab, so dass das neue Album No One von Horror Business Records als CD veröffentlicht wurde. Horror Business Records übernahm die Vermarktung des Albums. Musikalisch ist das Album von Paranoya zwischen Hardcore und Punk anzusiedeln. Während bei den Demos der Band der Drei-Akkorden-Punk dominierte, sind auf diesem Longplayer diverse Hardcore- und leichte Metal-Anleihen zu hören. Bei den Reviews diverser Fanzines wurde des Öfteren der Vergleich mit Rawside angeführt. Durch Horror Business Records bekam die Band auch Reviews verschiedener Printmedien wie dem Ox, Plastic Bomb und dem Rock Hard.

Auch der Coolibri und der Westfälische Anzeiger schrieben über die Band. Während sie beim Plastic Bomb und kleineren Fanzines gut reviewed wurden, war das Ox etwas reservierter und beim Rock Hard fiel No One durch. Es folgten weitere Auftritte mit Rantanplan, Scattergun, Pascow, als auch szeneübergreifende Gigs mit Delirious, Cuatro X, u. a. Auch zu diversen Samplern steuerten Paranoya Lieder bei und sie spielten Konzerte in der ganzen Bundesrepublik. Ein neues Album war auch in Planung, kam allerdings durch bandinterne Differenzen ins Stocken, woraufhin Lars W. 2004 die Band verließ. Paranoya hatten zwar neues Material für ein Album zusammen, suchten allerdings einen neuen Bassisten. Für das neue Album sollte erst mal als Studiobassist Marco Schuster, der schon bei Cuatro X Bass spielte, den Part übernehmen. Aus dem kurzfristig geplanten Engagement 2004 entstand mehr und Marco Schuster ist seitdem ein dauerhaftes Bandmitglied.

2004 begab sich die Band dann wieder ins Studio, um das neue Album Atmen einzuspielen, die Soundqualität überzeugte allerdings nicht, so dass dieses Demo nicht veröffentlicht wurde. Um nicht ganz von der Bildfläche zu verschwinden, brachte die Band 2005 eine Live-CD in Eigenregie heraus und spielte weiterhin live.

2007 startete man dann den zweiten Versuch, das Album Atmen aufzunehmen. Dabei wechselte man das Studio und begab sich ins Tonstudio Bunkeretage 2.e.V. in Duisburg. Im Gegensatz zur ersten Version von Atmen, wurde dieses Album dann von Major Threat (Sublabel von Horror Business Records), Unkrautrec. und das bandeigene Label Pararec. auf Vinyl und CD 2008 veröffentlicht. Musikalisch ist das Album Atmen das bis dahin abwechslungsreichste der Band, während das Vorgängeralbum stark vom Hardcore Punk beeinflusst war mit kleineren Ausflügen in ruhige Parts, wechseln sich bei Atmen schnelle und Midtemposongs ab. Man bedient sich aus den verschiedenen Punk-Subgenres sowie leichten Rockabilly- und Metal-Anleihen. Waren auf dem Vorgängeralbum auch viele englische Texte vorhanden, befinden sich auf dem Album Atmen nur noch zwei Lieder in Englisch. Die deutschen Texte zeichnen ein eher düsteres Bild und sind zum Teil autobiografisch als auch sozialkritisch angelegt, eine textliche Grundhaltung der Band.

Das neue Album wurde innerhalb der Szene positiv aufgenommen, abgesehen von den englischen Titeln. Durch die D.I.Y.-Szene gelangte das Album auch wieder in die USA, die Schweiz, Polen, England u. a. und wurde dort von diversen Independent-Radios gespielt. Mit dem neuen Album im Rücken spielte Paranoya dann zahlreiche Konzerte, unter anderen mit den Real McKenzies, Klasse Kriminale, Supabond und Oi Polloi. Als Highlight bezeichnete die Band vor allem den Auftritt mit der kanadischen Punkband D.O.A.

2011 bis heute

2011 kamen weitere Auftritte mit namhaften Bands zustande wie Dritte Wahl, Supabond, Cut my Skin und BicahunaS hinzu. In dieser Zeit bereitete sich die Band auf die Aufnahmen von neuem Material vor. Wieder ging es nach Duisburg ins Tonstudio Bunkeretage 2.e.V. und man nahm die 7"-Vinyl-EP Beobachter auf. Veröffentlicht wurde diese dann 2012 bei Major Threat und Pararec. Auch ein MP3-Download der Single war möglich, welchen das Plastic Bomb für die Band einrichtete. Auf dem Release sind vier Stücke der Band zu hören. Während die A-Seite musikalisch eher experimentell klingt, ist die B-Seite vom klassischen Punkrock der 77/78er gekennzeichnet. Der Opener Beobachter, gesungen von Daniel "Zwiebel" Jacobs, kommt ohne Refrain aus und das Stück Kunst enthält innerhalb der abgehackt gespielten Gitarrensequenzen, einen klassischen Rockabilly-Part mit Harmoniumsound im Hintergrund. Zwar gibt es mit Uncertain auf der B-Seite einen englischen Songtitel, allerdings ist nur der Refrain auf Englisch. Das Lied, das schon auf dem Album No One zu hören war, wurde neu eingespielt und mit einem neuen Text versehen. Textlich handelt es sich bei der EP Beobachter um ein ungewolltes Konzeptalbum mit dem Thema "Neue Medien".

Die Reviews zur Platte waren zwiegespalten. Während einige Punk-Zines sehr positiv auf die Vermischung verschiedener Stile und die Entwicklung der Band reagierten, schreckte das andere Zines eher ab. Auch diese Platte gelangte durch die D.I.Y.-Szene ins Ausland, wie USA, England, Schweiz, Polen, Ukraine, Schweden usw. Dies wurde auch begünstigt durch das als Spaß gegründete Label Pararec. als Onlinelabel. Dadurch gelang es Paranoya nicht nur die EP Beobachter auf den gängigen Musikplattformen im Internet zu veröffentlichen, sondern auch die Vorgängeralben Atmen und No One.

2013 war Paranoya mit der neuen EP in der Republik unterwegs und spielten als Support von Jaya the Cat, sowie zusammen mit den Dödelhaien und TZN Xenna aus Polen.

2014 trat die Band auf dem Fusion Festival auf, was ein weiteres Highlight der Band war.

Auf ihrer Homepage veröffentlichten Paranoya ein komplettes Live-Album zum freien Download. Dort konnte man schon einige Stücke zum kommenden Album finden. Im Frühjahr 2014 waren Paranoya wieder im Tonstudio Bunkeretage 2 e.V. in Duisburg, um das nächste Album aufzunehmen, das September 2015 unter dem Namen Fragmente erschien. Aus den Aufnahmesessions zum Album Fragmente resultierten zwei zusätzliche Songs, die im März 2017 als 7"-Vinyl-Single unter dem Titel Dämonen veröffentlicht wurden. Insbesondere das titelgebende Stück weicht kompositorisch und gesanglich mit Einflüssen aus Country und Folk stark vom bisherigen Schaffen der Band ab. Am 30. Dezember 2017 spielten Paranoya auf Punk im Pott mit Szenegrößen wie Dritte Wahl und Knochenfabrik.

Im Herbst 2018 verließ Thorsten Grams die Band und konnte noch vor dem Jahreswechsel durch Ben Postler am Schlagzeug ersetzt werden.

Im Herbst 2019 kam es zu einem weiteren Wechsel, Peter Hillebrand folgte Marco Schuster am Bass.