Der älteste Teil des Gebäudes in der Frankfurter Straße 12-14 wurde mit einer Sandsteinfassade 1907 durch die Firma Gebrüder Hasenbach gebaut. 1929 übernahm die Leonhard Tietz AG, gegründet 1879 in Stralsund, das Haus mit den Grundstücken Frankfurter Straße 12 bis 16.
Ein Jahr später wurde das Gebäude zur Frankfurter Straße 16 hin inklusive einer Sandsteinfassade erweitert. Die Leonhard Tietz AG war zu dieser Zeit eine der größten Kaufhausketten in Deutschland. 1933 wurde die Gründerfamilie wegen ihrer jüdischen Herkunft von den Nationalsozialisten enteignet. Die Kaufhauskette wurde in Westdeutsche Kaufhof AG umbenannt. So entstand der Name Kaufhof, der schließlich zu Galeria Kaufhof wurde.
Ende der 1950er Jahre ließen die Eigentümer der Immobilie "Deutsche Bank" und "Metro AG" bei einer erneuten Erweiterung und einem Dachumbau die Sandsteinfassade ab dem 4. OG komplett abtragen und durch eine Betonkonstruktion ersetzen.
Bei der letzten umfangreichen Gebäudemodernisierung im Jahr 1968 übernahm die Kaufhof AG auch das Eckgebäude Frankfurter Straße 18/Herrnstraße. Dieses wurde abgerissen und durch einen Betonanbau ersetzt, der auch dem heutigen Gebäudekörper entspricht.
In diesem Zusammenhang hat der Kaufhof die komplette Fassade der Frankfurter Str. 12-18 und der Herrnstraße mit einer vorgehängten Blechfassade verkleidet, wie es deutschlandweit an vielen Kaufhof-Gebäuden üblich war. Zur Befestigung der Alu-Platten wurden mehrere Stahlträger in der alten Fassade verankert, wodurch Teile der historischen Fassade beschädigt wurden. Seit Ende der 1960er bis in die 2020er Jahre wurde das Gebäude als Kaufhof genutzt.
