Si l’on désire réellement remonter au plus haut de la généalogie de Paris Violence, on peut peut-être en dater les premiers pas de 1991-1992, lorsque Flav (voix et guitare) et Jérôme (batterie) décident de jouer plus ou moins régulièrement ensemble. Assez vite, c’est Thierry qui remplace Jérôme à la batterie, le second continuant cependant d’apporter régulièrement une participation intermittente. En 1993, un premier choix décisif est fait: celui d’utiliser une boîte à rythme afin de donner aux compositions un aspect plus froid et mécanique et de s’inscrire dans la lignée des groupes comme Pigalle ou Métal Urbain qui déjà influencent beaucoup les compositions.
Mais c’est en 1994 la véritable naissance de Paris Violence, parmi plusieurs noms proposés par Flav, Thierry choisit: « Violence à Paris », proposant d’intervertir et d’inverser les deux termes pour rendre un effet plus percutant. Par ailleurs, l’achat d’un 4-pistes oriente d’ores et déjà le groupe vers un travail d’enregistrement et de recherche sonore au détriment d’une éventuelle présence scénique. Le répertoire est alors varié, alliant à une dominante punk des genres divers allant de la new-wave à chanson réaliste. C’est à cette période que les premiers véritables morceaux sont composés, dont « Angoisse », « Les complexes d’Alphonse Larvis », « Sur le front », « Spleen et banlieue », « Nuits urbaines » et bien d’autres – qui passeront à la trappe. Les textes, toujours rédigés par Flav, trouveront peu à peu leur tonalité propre: réalisme urbain, grisaille, déprime, vision désabusée du monde contemporain. Quant à la répartition des rôles, elle se fixe peu à peu avec Flav à la voix, à la guitare, aux claviers et aux programmations diverses, Thierry à la seconde guitare, aux claviers et aux chœurs, Jérôme aux chœurs.
En 1995 est enregistrée une première K7 démo, L’Esprit français qui, volontairement, ne circule que très confidentiellement. La tonalité en est très punk-rock, et l’essentiel des ingrédients du style Paris Violence sont déjà en place. Certains titres seront enregistrés avec le line-up complet, d’autres en duo Flav-Thierry, d’autres encore par Flav seul, qui prend déjà des habitudes de travail isolé. D’autres cassettes, réunies récemment sous le titre de La Préhistoire de Paris Violence (Paris 95, Voyage 32), sont également éditées… à un exemplaire ! Suit une seconde démo en 1996, Un Hiver en banlieue, où la voix de Flav commence à prendre la teinte Oi! qu’elle gardera par la suite.

1997 marque une seconde naissance pour le groupe, qui se décide enfin à tenter de se faire connaître via une participation de deux morceaux sur la compilation K7 Une façon de voir les choses  éditée par Islika Produktions, label underground monté par Flav pour l’occasion. S’y côtoient Zabriskie Point, Tarif Réduit, les Imbibés, DKP et Matricule 77. Parallèlement sort la troisième démo, Violence dans l’Azur, plus longue (1 heure) et plus aboutie que les précédentes, et, surtout, chroniquée dans la presse punk et disponible chez les distributeurs VPC. Paris Violence sort enfin de l’anonymat et prépare la quatrième et dernière démo, De Colère et de Haine, bouclée en août 1997 mais diffusée qu’à partir de janvier 1998 pour ne pas trop télescoper la précédente.
C’est alors que trois propositions parviennent quasi simultanément: la première vient de Carnage Records, nouvelle appellation de One by One rds (Anti-Patik, Dickheads..) qui désire, sur la lancée de ses compilations Oi! It’s the party Time…, lancer une nouvelle série de 45 tours 4 groupes. Un seul volume en verra cependant le jour, sous le nom de More Oi!, Punk-rock and sexy Girls for the Boys, avec Stoicks, Dicheads, Les Contaminés et Paris Violence. En fait si le disque est prêt courant 1998, ce n’est qu’en 1999 qu’il sortira dans les bacs suite à des problèmes de douane.
La seconde vient de Rural Muzik (Melmor, Phase terminale…), qui offre de produire un premier EP. Ce sera le 4 titres Humeurs noires, enregistré à la hâte sur 4-pistes dans l’appartement de Flav. Malheureusement, l’usine commet une erreur de pressage, augmentant la vitesse de la face A! Peu importe, Paris Violence a enfin la gratification d’avoir sorti un premier disque. Quant à la version « réelle » des titres, il faudra le volume 1 de la singles collection Du Futur faisons Table rase, sorti exactement dix ans après, pour les entendre.
Quant à la troisième proposition, c’est celle de Lion Records (West Side Boys, Urban Gones, Kro Men) qui désire également sortir une compilation 45 tours avec quatre groupes Oi!. Finalement, le projet se transforme en EP avec Paris Violence seul puis, après réflexion, en album CD coproduit avec Islika Produktions. C’est ainsi qu’est lancé Temps de Crise, comprenant des titres tirés des deux dernières démos, de nouvelles versions d’anciens titres et de nouveaux titres.
Enfin, 1998 est également l’année de Violence urbaine, split EP avec Symphonie Urbaine (deux morceaux par groupe) chez le label Fraktion Provisoire, qui produira plus tard le troisième album.