1899 beschlossen die Großherzoglich Badischen Staatseisenbahnen den Bau zweier neuer Salondampfer für die Konstanzer Flotte. Beide Schiffe sollten von der Maschinenfabrik Gebrüder Sulzer in Winterthur gebaut werden. Weil diese aber nur die fristgerechte Fertigstellung der Stadt Meersburg garantieren konnte, ging der Auftrag für das zweite Schiff an die Werft der Gebrüder Sachsenberg in Roslau (Elbe). Die Stadt Konstanz ersetzte den GD Friedrich.
Erste technische Mängel wurden von der Firma Gebrüder Sulzer im Zeitraum vom 27. Juli 1902 bis zum 30. Mai 1903 durch eine Verlängerung mittels Einfügen von zwei je 1,5 Meter langen Segmenten auf eine Gesamtlänge von 58,14 Meter sowie den Einbau eines größeren Hochdruckzylinders mit Ventilsteuerung behoben. Danach war die Stadt Konstanz bis 1929 das schnellste Dampfschiff auf dem Bodensee und wurde deshalb überwiegend im Kursverkehr Konstanz–Bregenz eingesetzt.
Die Reichsbahn baute die Stadt Konstanz im Gegensatz zu gleichaltrigen Schiffen in den 1930er Jahren nicht um und musterte sie bereits nach 36 Dienstjahren 1937 aus. Ersetzt wurde sie durch das MS Karlsruhe. Im Frühjahr 1939 erfolgte der Abbruch des Salondampfers.