Teren, na którym dzisiaj znajduje się Plac Zwycięstwa był miejskim stawem, rozciągającym się przed Nową Bramą. Staw wraz z rozlewiskami został w połowie XIX w. zasypany piaskiem z Lasku Północnego. W latach 1848÷1855 z wyrobiska w lasku wywieziono ponad 19 tysięcy furmanek piasku. W wyrobisku pozostałym po piaskowni w latach 1924÷1926 zbudowano reprezentacyjny stadion sportowy, któremu w dniu 15 sierpnia 1926 roku uroczycie nadano imię feldmarszałka Rzeszy Niemieckiej Paula von Hindenburga. Natomiast w miejscu, w którym znajdują się dziś fundamenty ratusza, rozciągały się bagna i torfowiska, a miejsce to było nazywane Placem Wełnianym. 7 stycznia 1931 r. plac ten przemianowano (w stulecie urodzin) na Plac Stephana, od nazwiska genialnego, słupskiego poczmistrza Heinricha von Stephana.

Równolegle z frontem inżynieryjnych robót ziemnych i zdrenowaniem terenu pod zabudowę, ogłoszono konkurs na projekt ratusza. Na konkurs napłynęło aż 87 propozycji 486 architektów z całych Niemiec. Sąd konkursowy odbył się 16÷17 maja 1898 r. w szkole elementarnej przy dzisiejszej ulicy Deotymy (Wollmarktstrasse). W skład komisji wchodzili: profesor Ende z Berlina, urbaniści Meyer i Pluddeman, bogaty słupski kupiec Karl Frank i oczywiście burmistrz Matthes.

Po dwóch dniach narad, komisja ogłosiła, że wybrała do realizacji projekt prof. Karla Zaara i inżyniera Rudolfa Vahla pt. "Format staroniemieckiego gotyku", z którymi już miesiąc później władze miejskie podpisały umowę. Projekt ten, zakładał powstanie budynku o 23176 metrów sześciennych kubatury i opiewał na końcową sumę około 300.000 marek. Druga nagroda w konkursie przypadła szkicowi "Anastassia", autorstwa berlińskich architektów Schulza i Schlichtinga. Na trzecim miejscu sklasyfikowany został "Plattdeutsch" projektu berlińczyków Meiera & Werlea.

W kwietniu 1899 roku prace ruszyły pełną parą. Już jednak na samym wstępie pojawiły się duże trudności, gdyż dało o sobie znać wyżej wspomniane bagienne podłoże. Fundamenty ratusza trzeba było wykonać bardzo kosztowną na owe czasy, techniką kesonową. Polegała ona na wbiciu w torfowe podłoże osiemnastu betonowych pali, każdy z nich ma 5,5 metra długości. O ile jednak, na decyzję o zabudowie urzędnicy musieli czeka ponad dziesięć lat, o tyle sama budowa ratusza została wykonana w zaskakująco krótkim czasie. W sobotę 22 września 1900 roku zawieszono na dachu magistratu wiechę, co stało się okazją do świętowania. Zebrani przed placem budowy mieszkańcy, włodarze i wykonawcy mieli okazję wysłuchać przemówienia majstra Heinemnana, wygłoszonego prosto z ozdobionego na tę okazję rusztowania. Uroczystości zakończyły się suto zakrapianym bankietem w hotelu Kleina (dzisiejszym Staromiejskim), a wszystkim rzemieślnikom pracującym przy budowie ratusza zafundowano darmowe piwo. Radcy miejscy przeznaczyli na ten cel kwotę 600 marek.

Niecały rok później, w dniu 5 lipca 1901 miejscowa gazeta odnotowała: "[...]Przy wspaniałej pogodzie miała miejsce wczoraj po południu inauguracja naszego, nowego ratusza. Domy w mieście ozdobione były flagami. Uroczystość rozpoczęła się po południu o godz. 16.45 odegraniem chorału "Chwalmy Pana" z wieży ratuszowej, do którego dołączyły dźwięczne fanfary heroldów. W tym czasie do sali ratuszowej przybyli przedstawiciele miejscowych i zamiejscowych władz oraz goście honorowi - fundatorzy darowizn. Jego ekscelencja nadprezydent von Maltzahn i przewodniczący okręgu rewizyjnego pan von Tapper-Laski o godz. 17.00 wprowadzili burmistrza Matthesa do sali posiedzeń[...]". Tak właśnie rozpoczęło się pierwsze posiedzenie Rady Miejskiej w nowym budynku Magistratu.

Trzeba przyznać, że nowy ratusz w neogotyckim stylu doskonale współgrał z bramami i kościołami ówczesnego Słupska, zaś asymetria fasad budynku doskonale uzupełniała się z bliskim otoczeniem. Okazały plac przed głównym wejściem, przez wiele lat służył za miejsce organizowania jarmarków i miejskich festynów. Za ojca tego sukcesu uchodził burmistrz Matthes. Niestety okazało się, że koszty budowy ratusza ostatecznie dwukrotnie przerosły oszacowany budżet budowy. Kiedy przekonano się, że kasa miejska ma dwa miliony marek długu, nikt już nie pamiętał o zasługach i innych, miejskich inwestycjach burmistrza, którego w 1905 roku z wielkim hukiem wyrzucono z zajmowanego urzędu.