Nachdem sich Lutz Schulenburg und Pierre Gallissaires kennengelernt hatten und Hanna Mittelstädt 1972 zu ihnen gestoßen war, gab das Trio zunächst die Zeitschrift MAD (Materialien – Analysen – Dokumente) heraus, bevor 1973 das erste Verlagsprogramm unter demselben Namen erschien, der 1977 nach einer Klage des gleichnamigen Satiremagazins in Edition Nautilus geändert wurde. Seitdem hat der Verlag fast 1.000 Titel produziert. Es wurden 63 Bände der Kleinen Bücherei für Hand und Kopf verlegt, 14 Bände der Franz-Jung-Werkausgabe (jeweils in Paperback und Leinen gebunden), 19 Bände der Kurzkrimireihe Kaliber .64, 31 Nummern der Zeitschriften MaD und Revolte! (digitalisierte Ausgaben hier) und stolze 220 Nummern der Aktion (in 80 Ausgaben) sowie, »same procedure as every year«, sieben Dialektvariationen von Dinner for one in Buchform.
Nachzulesen ist die Geschichte der ersten vierzig Jahre des Verlags in Hanna Mittelstädts Buch Arbeitet nie! Die Erfindung eines anderen Lebens. Chronik eines Verlags (2023) – wobei der erste Teil des Titels in der gesamten Verlagsgeschichte nur sehr selten beherzigt wurde: Zu den Schriften der Anarchisten und Situationisten, die vor allem Pierre Gallissaires aus dem Pariser Mai 1968 mitgebracht hatte und die nach gemeinsamer Übersetzungsarbeit auf deutsch zugänglich gemacht wurden, gesellten sich ab 1980 die ersten Autobiografien: Der Todestrieb von Jacques Mesrine, Beneath the Underdog von Charles Mingus, Lady sings the Blues von Billie Holiday und andere. Dazu kam unerschrockene Prosa junger Autor*innen wie Franz Dobler, Ingvar Ambjørnsen, Anna Rheinsberg oder Sean McGuffin.
Parallel dazu wurde die Werkausgabe von Franz Jung in Angriff genommen und 1997 mit 14 Bänden
abgeschlossen. Diese fast komplett förderungsfreie Edition ging sehr zu Lasten der Verlagsökonomie, die in der Edition Nautilus stets um einige wenige Verkaufserfolge herum organisiert werden musste, etliche Jahre lang etwa um den zweisprachigen Silvester-Dauerbrenner Dinner for One.
Die Veröffentlichung dreier Bücher von Karl-Eduard von Schnitzler, dem umstrittenen Chef-Kommentator des DDR-Fernsehens, war keineswegs die erste und auch nicht die letzte absichtsvolle programmatische Grenzüberschreitung des Verlags, aber ökonomisch geradezu ein Geniestreich, ermöglichte der Verkaufserfolg ausgerechnet dieses Autors doch die Herausgabe von Abel Paz’ großer Biografie Durruti. Leben und Tode des spanischen Anarchisten.
Ökonomisch wenig erfolgreich, aber unverzichtbar war Die Aktion, herausgegeben von Lutz Schulenburg und eine der letzten streitbaren Zeitschriften für Politik, Literatur und Kunst, die Hanna Mittelstädt mit einer Hommage-Ausgabe für Lutz Schulenburg im September 2013 eingestellt hat.
Ein erfreulich zahlreiches Lesepublikum hingegen eroberten auch die Bücher von Wiglaf Droste, Subcomandante Marcos, Paco Ignacio Taibo II (vor allem dessen Che-Guevara-Biografie) und auch einige Titel aus der Kleinen Bücherei für Hand und Kopf, etwa die Grotesken von Kurt Schwitters oder die Aphorismen von Francis Picabia. Dessen Motto »Unser Kopf ist rund, damit das Denken die Richtung wechseln kann« gibt nach wie vor ein zuverlässiges Verlagsmotto ab – zuverlässiger jedenfalls als »Arbeitet nie!«
Im neuen Jahrtausend konnte das Nautilus-Programm die Folge der »Schwarz-Roten Ziegel« um weitere Kompendien der Basisbewegungen erweitern: etwa um den berühmten Wälzer von Horst Stowasser, Anarchie!, eine überarbeitete Neuausgabe der Autobiografie von Emma Goldman, Gelebtes Leben, ein Handbuch zur Direkten Aktion von David Graeber, das 600-Seiten-Werk Schwarze Flamme von Lucien van der Walt und Michael Schmidt oder die Biografie über die Anarchistin Lucy Parsons, Göttin der Anarchie von Jacqueline Jones. Mit Michael Warschawski, Mahmood Mamdani, Eyal Weizman oder Gilbert Achcar holte die Edition Nautilus hochkarätige internationale Gesellschaftskritiker an Bord. Beiträge zur Zeitgeschichte der BRD lieferten u.a. die Zeugnisse ehemaliger Protagonist*innen des bewaffneten Kampfes: Inge Viett, Karl-Heinz Dellwo, Gabriele Rollnik.
Die Krimisparte des Programms wurde 1988 mit der ›Schwarzen Trilogie‹ Léo Malets begründet. Ein Krimi war es auch, der dem Verlag dann seinen zahlenmäßig bisher größten Erfolg einbrachte: Tannöd von Andrea Maria Schenkel, im Februar 2006 in einer vorsichtig kalkulierten Auflage von 2800 Exemplaren erschienen. Das Krimidebüt zog daraufhin weite Kreise, und ein Jahr nach der Veröffentlichung landete es auf der Spiegel-Bestsellerliste, wo es wochenlang Platz 1 besetzte, bis der zweite Krimi der Autorin, Kalteis, ihn auf Platz 2 verdrängte. Für beide Werke wurde sie mehrfach ausgezeichnet, Tannöd wurde in mehr als 20 Sprachen übersetzt und verkaufte sich in allen deutschsprachigen Ausgaben zusammengerechnet eine Million Mal.
Durch diesen fast märchenhaften Erfolg konnte das inzwischen gewachsene Verlagsteam aus den drei Büroräumen über einer Einkaufspassage in der Bergedorfer Fußgängerzone im Dezember 2008 in das ehemaliges Fabrikgebäude in Hamburg-Bahrenfeld ziehen, wo wir heute noch ansässig sind.
Seit Gewährsleute im Jahr 1994 den mit ganz anderen schnöden Alltagsdingen beschäftigten Verlag darauf hingewiesen haben, dass dieser doch schon zwanzig Jahre lang bestehe, werden die Jubiläen, passend zur Seriosität des Verlags, jeweils am 1. April aller auf 4 endenden Jahre gefeiert (am 18. April 1974 hatte Lutz Schulenburg nach Erreichen der Volljährigkeit das Gewerbe nachträglich auf seinen Namen angemeldet). Das vierzigste Jubiläum 2014 stand dann allerdings im Schatten des Todes des Verlegers, der am 1. Mai des Vorjahres nach kurzer schwerer Krankheit unerwartet gestorben war.
Als gut aufeinander eingespieltes Kollektiv ohne geheimes Chef-Wissen konnten wir die Nautilus auch ohne seine subversive Größe durch bewegte Gewässer steuern, obwohl Lutz uns schmerzhaft fehlt. 2016 übergab Hanna Mittelstädt als Letzte aus dem Gründertrio den Verlag ihrer Crew, damals bestehend aus Klaus Voß, Katharina Picandet, Franziska Otto, Katharina Florian und Katharina Bünger, teilweise seit über 20 Jahren im Verlag. Seitdem machen wir weiter Bücher im unkonventionellen, eigenwilligen und kämpferischen Geist, der die Edition Nautilus schon immer geprägt hat.
Immer wieder wurde der Verlag auch mit Preisen geehrt, so im Jahr 2004 mit dem Kurt-Wolff-Preis, der für das anspruchsvolle literarische Programm, für die Künstlerbiografien und die Herausgabe der Franz-Jung-Werke verliehen wurde. Die Edition Nautilus erhielt für ihr außergewöhnliches Programm außerdem 1993 und 2002 den Verlagspreis der Freien und Hansestadt Hamburg sowie 2018 den Karl-Heinz Zillmer-Verlegerpreis. 2019 und 2020 wurden wir mit dem Deutschen Verlagspreis ausgezeichnet.
Hanna Mittelstädt hat 2022 die Hanna Mittelstädt und Lutz Schulenburg Stiftung gegründet, die sich der Bewahrung, Erforschung und Förderung der wesentlichen Traditionslinien des Verlags von 1972 bis 2013 sowie der Werke Franz Jungs verschrieben hat.
Der Verlag bereitet sich inzwischen auf das im Frühjahr 2024 zu feiernde 50. Jubiläum vor.