Die Geburtsstunde von Nautilus war eine Nachrichtensendung am 18. November 1998, welche ist im Logbuch der Nautilus nicht mehr vermerkt. Der Nachrichtensprecher verkündete, eine Trägerrakete sei erfolgreich ins Weltall gestartet und habe ein Modul für die Raumstation ISS (International Space Station) an Bord. Dieses Modul ist und war der grundlegende Baustein der Raumstation, an der sich heute Nationen aus der ganzen Welt beteiligen.
Kurze Zeit später erzählte Wolfgang Brigitte von diesem Start und der Idee, die gemeinsame Konstruktion einer Weltraumstation zum Gegenstand eines Spiels zu machen. Als Deep Space Nine Fan hatte Brigitte sofort die Idee, dass an Bord dieser Station verschiedene Völker mit unterschiedlichen Eigenschaften sein müssten. Die Idee wurde noch weiter verfeinert. So wurden Überlegungen in Richtung Forschungsexpeditionen angestellt, die noch unbekannte Planeten nach Bodenschätzen und Leben absuchen sollten. Zudem müsse es hierbei je nach Natur des Weltraumvolkes unterschiedliche Ziele geben.
Wenige Tage zuvor war unser drittes Kind Raphael zur Welt gekommen.So beanspruchte die Familie sehr viel Zeit und die Idee ruhte vorerst. Da keine Kinder zugelassen sind, besuchte nur Wolfgang die Spielwarenmesse in Nürnberg 1999. Dort wurde u. a. durch eine Schachtel auf ein großes Weltraumspiel hingewiesen: Die Sternenfahrer von Catan. Als Science-Fiction-Fans wussten wir, dass sich Spiele mit solchen Themen nicht übermäßig durchgesetzt haben und wenn Catan nun den Weltraum erobert, konnte es unser Spiel nicht tun. Wir empfanden es nicht als traurig, sondern warteten eher auf die Sternenfahrer, die sich bei uns mit ihrer Zweipersonenvariante Sternenschiff Catan dann großer Beliebtheit erfreuten.
Uns gefielen die Ideen - das Spiel hatte zu diesem Zeitpunkt immer noch keinen Namen - zu sehr, um sie fallen zu lassen.
Ziemlich schnell verlegten wir den Ort des Geschehens: In einer Unterwasserstation leben Forscher mit verschiedenen Aufträgen, die zur Erforschung des Meeres die Station in U-Booten verlassen. Während die Weltraumversion nie das Licht dieser Erde erblickte, wurde die Unterwasserversion tatkräftig umgesetzt und das Spiel erhielt einen Arbeitstitel: Tiefsee.