Das 1978 in Reserve gegangene MS Kempten konnte zwar noch auf schwächer frequentierten Nebenkursen eingesetzt werden, war aber Ende der 80er Jahre nicht mehr zeitgemäß.
Deshalb gab die Dte. Bundesbahn erstmals nicht bei der Bodanwerft, sondern bei der ÖSWAG Korneuburg, mit Außenstelle in Fussach ein Dreideckmotorschiff, in der Größe des MS Konstanz in Auftrag.
Am 18.03.1989 konnte das Schiff unter dem Namen des Luftschiffpioniers Graf Zeppelin in Friedrichshafen in Dienst gestellt werden.
Dieses moderne, formschöne Schiff, bei dem die Motorenanlage erstmals auf einem dten. Schiff im Heck untergebracht ist, ersetzte das erste Bodenseemotorschiff mit Voith-Schneider-Antrieb das MS Kempten, das bis Sommer 2000 im Konstanzer Hafen verankert war und 2001 abgebrochen wurde.
Das MS Graf Zeppelin, das hauptsächlich für Sonder- und Charterfahrten eingesetzt wird, erhielt die Schiffsglocke des 1963 ausgemusterten Dampfers Stadt Überlingen II.
Dieses, von den anderen Motorschiffen durch sein modernes, hochseemäßiges Aussehen gut zu unterscheidende Schiff, wird sowohl vom offiziellen Heimathafen Friedrichshafen, als auch vom Hafen Konstanz aus eingesetzt.
Seit der Saison 1999 wird das MS Graf Zeppelin auch vermehrt als Kursschiff ab Friedrichshafen eingesetzt.
Im Frühjahr 2007 wird MS Graf Zeppelin in der Werft in Fussach umgebaut. Das Heck wird um ca. 5 Meter verlängert, zudem erhält das Schiff einen Bugwulst und Schlingerkeile an den Rumpfseiten. Damit soll der Treibstoffverbrauch um 25 % verringert und die Wellenbildung vermindert werden.
Im Winter 2011/2011
wird MS Graf Zeppelin in der Friedrichshafener Werft generalüberholt.
Dabei bekommt das Schiff einen komplett weißen Anstrich und neue Schriftzüge.
MS Graf Zeppelin wird neben Sonder- und Charterfahrten überwiegend für
Oberseekursfahrten ab Friedrichshafen eingesetzt.