Budynek poczty głównej na rogu ulic Łukasiewicza i Mikołajskiej zbudowano w 1879 roku. Jednak w tym miejscu poczta funkcjonowała już od 1814 roku w dwóch budynkach (wówczas Predigerstr. 205 i 206), które stały od strony ulicy Łukasiewicza. Były one dzierżawione od prywatnych właścicieli aż do 1878 roku, a więc do czasu ich zakupu przez pocztę. Kupiono również trzy okoliczne zabudowane parcele od strony dzisiejszej ul. Mikołajskiej (wówczas Butterstr. nr 208, 209 i 210). Po wyburzeniu wszystkich budynków na rogu obecnych ulic Łukasiewicza i Mikołajskiej postawiono nowy, murowany gmach poczty głównej i telegrafu. Budynek zbudowano na planie litery L ze ściętym narożnikiem, w którym umieszczono główne wejście do budynku poczty. Bryłę wzbogacono ryzalitami z trójkątnymi szczytami. Nad ryzalitem narożnym z głównym wejściem wzniesiono wieżyczkę z zegarem. Po bokach ozdobnych drzwi usytuowano kamienne kolumny tworzące arkadę z łukiem i dźwigające balkon. Elewacje wyłożono cegłą klinkierową koloru pomarańczowego z ozdobnymi pasami w kolorze ciemniejszym, a ponadto wzbogacono kolorystycznie ciemnozielonymi płytkami ceramicznymi pod oknami. Część cokołową wyłożono płytami piaskowca. Styl neogotycki podkreśla detal architektoniczny w postaci fryzów z czwórliści i rozetek biegnących przez całą długość ścian pod gzymsem i pod oknami, czołganki na krawędziach szczytów oraz krenelaż wieńczący ścianę północną. Pod względem architektonicznym całość nawiązywała stylem do stojącego w pobliżu kościoła Najświętszej Marii Panny. Nowy gmach poczty spełniał nie tylko funkcję urzędowe, ale również kwaterunkowe. Mieszkał w nim dyrektor,  a także listonosze i pracownicy poczty.

Intensywny rozwój miasta, wzrost liczby mieszkańców, instalowanie w mieście sieci telegraficznej i zapotrzebowanie na usługi pocztowe spowodowały, że już na początku XX wieku budynek przestał wystarczać. Aby temu sprostać kupiono dwa stojące od strony ulicy Łukasiewicza budynki (wówczas Predigerstr. nr 5 i 6), zburzono je i do gmachu od strony zachodniej dobudowano przybudówkę.

Poczta główna została zajęta w marcu 1945 roku przez rosyjskie wojska łączności i stanowiła składnicę zdobyczy wojennych. Po interwencji pełnomocnika rządu 15 lipca 1945 roku władze radzieckie przekazały Polakom obiekt i od tego dnia usługi pocztowe w Słupsku zostały uruchomione we wszystkich działach: listowym, pieniężnym, telefonicznym i telegraficznym. W 1993 roku do budynku poczty dobudowano gmach telekomunikacji. Cztery lata później przeprowadzono remont elewacji budynku poczty oraz modernizację jej wnętrza. Sale obsługi ozdobiono drzwiami, ławami i innymi detalami, których stylistyka świadomie nawiązuje do form neogotyckich dla podkreślenia takiego właśnie charakteru zabytkowej budowli. 20 listopada 1999 roku odsłonięto tablicę pamiątkową ku czci Heinricha von Stephana (1831-1897), rodowitego słupszczanina, generalnego poczmistrza cesarstwa niemieckiego i jednego z najważniejszych ministrów w ówczesnej Rzeszy. Stephan był twórcą Światowego Związku Poczty i ma wiele zasług i osiągnięć, które zrewolucjonizowały działanie poczt wielu krajów. Przedstawiono go na setkach znaczków pocztowych wydanych przez  większość państw świata.