Die Literaturstudenten Werner Labisch und Jörg Sundermeier gründeten den Verbrecher Verlag 1995. Zunächst suchten sie eine Möglichkeit, um an unveröffentlichte Manuskripte für private Lesezwecke zu kommen – sie hatten in Interviews oder Porträts von Manuskripten einiger ihrer Lieblingsautorinnen und -autoren gelesen, die in absehbarer Zeit nicht veröffentlicht werden sollten. Labisch und Sundermeier waren aber gierige Leser, sodass sie den Plan fassten, sich als Verlag auszugeben, um die Texte der geschätzten Autorinnen und Autoren eben doch lesen zu können, selbst dann wenn sie unveröffentlicht bleiben sollten.
Ein Verlag braucht einen Namen und sein Briefpapier einen Briefkopf. Der Verlagsname entstand, ebenso wie das Logo, aus einer Laune heraus, und hatte erst einmal den Zweck, bei den angeschriebenen Autoren wenig Hoffnung auf eine tatsächliche Publikation aufkommen zu lassen.
Auf diese Weise fragten Sundermeier und Labisch unter anderem Dietmar Dath, dessen Texte ihnen in diversen Zeitschriften aufgefallen waren, nach einem bestimmten Manuskript. Er bot ihnen daraufhin – anstelle eines anderen, bis heute noch nicht publizierten Textes, nach dem Labisch und Sundermeier gefragt hatten – die ersten beiden Kapitel eines Romans an, der zu diesem Zeitpunkt noch nicht vollendet war. Bei den Pseudoverlegern war damit das Interesse geweckt und sie vereinbarten ein Treffen mit dem Autor auf der Frankfurter Buchmesse 1994.
Bei dieser Gelegenheit bekamen die Neulinge auch einen ersten Eindruck vom Verlagswesen, ohne jedoch größere Ambitionen zu entwickeln. Als Dath ihnen jedoch das vollständige Manuskript mit der Anmerkung vorlegte, er habe es die letzte Nacht fertiggestellt, war die übliche schriftliche Ablehnung keine Option mehr. Zudem war das Manuskript sehr gut, und daher gaben sie den Roman „Cordula killt dich! Oder: Wir sind doch nicht die Nemesis von jedem Pfeifenheini“ im August 1995 als erstes Buch heraus. Der Verbrecher Verlag war Wirklichkeit geworden. Da sich das Geschäft für die beiden blutigen Anfänger allerdings schwieriger gestaltete als zunächst vermutet, entfernten sie sich vorerst wieder von der Arbeit im Verlagsgeschäft.
Diverse Zeitungs- und Werbeprojekte kennzeichneten die nach dem ersten Buch folgende verlegerische Schaffenspause. Sundermeier und Labisch wurden 1999 jedoch vom befreundeten Comiczeichner Oliver Grajewski zur Wiederbelebung des Verlags animiert. Sie verfügten damals bereits über ein Büro am Hackeschen Markt und die nötige Motivation und hatten gerade ein anderes Projekt abgeschlossen. So kam es dann zu dem zweiten Titel, der im Oktober desselben Jahres im Verbrecher Verlag erschien: „Tigerboy #16“ von Oliver Grajewski.
Die Verlagsarbeit ging von da an munter weiter: Eine Zeitungsanzeige des Verbrecher Verlags bewegte Stefan Wirner dazu, seinen Cut-Up-Text aus Zeitungsartikeln zum Jugoslawienkrieg anzubieten. „Installation Sieg“ erschien im Dezember 1999. Auch der Kontakt zu Dietmar Dath war immer noch eng, daher kam im März 2000 der Roman „Am blinden Ufer“ von ihm heraus. Die Verlagsarbeit gewann an Kontinuität. Drei Monate später suchte Jim Avignon, der mit seinem Projekt „Neoangin“ auf einer „Verbrecher Versammlung“ aufgetreten war, einen Verlag für sein neues Buch und fand auch thematisch einen Platz im Programm des Verbrecher Verlags.
Eine regelmäßige Einrichtung in Berlin wurden die „Verbrecher Versammlungen“. Von Dezember 1999 bis Mai 2004 fanden sie wöchentlich im Kaffee Burger statt. Es handelte sich bei den Zusammenkünften um Lesungen, Vorträge, Konzerte und andere publikumstaugliche Performances, welche sich großer Beliebtheit erfreuten. Von Februar 2005 bis Februar 2007 fanden die „Verbrecher Versammlungen“ im Festsaal Kreuzberg, seit dem März 2007 in der Bar Monarch, seit 2014 in der Fahimi Bar statt, alle unmittelbar am Kottbusser Tor gelegen. Sie finden zur Zeit an jedem 2. Dienstag im Monat statt, im Juni, Juli und August allerdings herrscht Sommerpause.
Seit September 2003 residiert der Verlag im Mehringhof, Gneisenaustraße 2a, in Berlin-Kreuzberg. Werner Labisch schied Ende 2010 aus dem Verlag aus. Seit 2016 leitet Jörg Sundermeier den Verlag gemeinsam mit Kristine Listau.
Inzwischen hat der Verlag über 300 Bücher herausgebracht. Er publiziert Sachbücher, Kunstbücher und Comics – vor allem aber Belletristik. Er widmet sich so etwa dem Werk von Gisela Elsner, Christian Geissler, Rudolf Lorenzen, Giwi Margwelaschwili und Erich Mühsam – und seine Editionen, teilweise sogar kritische Werkausgaben, werden von den Medien regelmäßig sehr gelobt. Weitere bekannte Autorinnen und Autoren des Verlags sind Darius James, Nino Haratischwili, Gunnar Gunnarson, Thomas Meinecke, Christian Y. Schmidt, Lisa Kränzler, Wolfgang Müller, Georg Kreisler, Chaim Noll, David Wagner, Elfriede Czurda, Irmtraud Morgner, Kolja Mensing, Peter O. Chotjewitz, Kathrin Passig oder Christian Broecking.
2014 wurde der Verbrecher Verlag auf der Leipziger Buchmesse mit dem Kurt Wolff Preis augezeichnet. Der Verbrecher Verlag erhielt den Hauptpreis, der Mairisch Verlag den Föderpreis. Die Begrüßung der Gäste durch Stefan Weidle, den Vorsitzenden der Stiftung, können Sie hier nachlesen. Dietmar Dath hielt dort eine wunderbare Laudatio, sie ist hier nachzulesen.
2016 wurde Jörg Sundermeier mit dem Karl-Heinz Zillmer-Preis für verdienstvolles verlegerisches Handeln ausgezeichnet.
2019 erhielt der Verbrecher Verlag gemeinsam mit dem Berenberg Verlag den Berliner Verlagspreis.
Der Verbrecher Verlag zählt zu den Preisträgern des Deutschen Verlagspreises 2019, 2020 und 2022.