Parcele, na których stanął hotel Kleina, wcześniej zajmowała duża stajnia garnizonowa oraz zabudowania zwrócone frontem do obecnej ulicy Piekiełko. Wówczas były to peryferia średniowiecznego miasta, a stojąca tu stajnia nikogo nie raziła. Gdy w latach 60. XIX wieku zaplanowano połączenie kolejowe z Koszalinem i Gdańskiem Słupsk czekała transformacja i nowe kierunki rozwoju. Ulica, którą dziś znamy jako Jedności Narodowej, wówczas nie istniała, a miasto w tym miejscu kończyło się na murach obronnych, które biegły równolegle do dzisiejszej ul. Murarskiej. Około 1866 roku w murze miejskim, na wysokości przedłużenia dzisiejszej ul. Filmowej, wybito dziurę, dzięki czemu możliwe stało się skomunikowanie miasta z placem budowy stacji kolejowej. Zanim to jednak nastąpiło w zabudowaniach dolegającym do dużej stajni, mistrz kowalski Gottfried Klein prowadził kuźnię, a także wynajmował pokoje i mieszkania. Gdy przebito mury, otwarte przejście wraz z krótką uliczką nazwano Am Bahnthor (obecnie ul. Jedności Narodowej). Ulice Piekiełko i Filmowa nabrały nowego znaczenia, a przed właścicielami działek nastały nowe możliwości.

Gustav Klein, syn kowala, w budynku przy ul. Piekiełko (obecnie nr 17) prowadził gospodę II klasy wraz z restauracją. Interes szedł świetnie i w zaledwie kilka lat po otwarciu Gustav przekształcił gospodę w "Hotel Klein", a do tego urządził tu skład win, alkoholi, papierosów i piwa. W latach 90. XIX wieku nadarzyła się okazja zakupu sąsiedniej działki wraz ze stojącą na niej stajnią. Klein bez wahania kupił nieruchomość, zburzył stajnie i przystąpił do budowy nowego, dużego i nowoczesnego hotelu, który ukończono w 1897 roku. Właściciel do starego hotelu przy ul. Piekiełko nr 17 dostawił trzykondygnacjowy budynek z narożną czterokondygnacjową wieżą oraz salą widowiskową, która stanęła na miejscu budynków gospodarczych. Wewnątrz hotelowo-rozrywkowego kompleksu było podwórze, do którego można było się dostać bramą od strony ul. Piekiełko (obecnie w bramie lokal handlowy). Od frontu były arkady, a więc nie wchodziło się bezpośrednio do hotelu i sali rozrywkowej z ulicy. W latach 1911-1912 budynek przeszedł renowacje i został powiększony. Goście mieli do dyspozycji ciepłą i zimną wodę na wszystkich kondygnacjach, łazienki, garaże, centralne ogrzewanie, światło elektryczne, a do tego pierwszej klasy kuchnię oraz dużą restaurację. W 1914 roku salę teatralną przebudowano na kino z prawdziwego zdarzenia. Zainstalowano 317 stałych foteli na parterze i 88 na balkonie pierwszego piętra. Do tego powstała garderoba, w jednym z pomieszczeń urządzono magazyn na filmy oraz salę kinooperatora, a kasę i wejście główne umieszczono w pierwszej i drugiej osi budynku. Podium (scena teatralna) zostało, bowiem do wielu niemych filmów przygrywała wówczas orkiestra.

Zaraz po pierwszej wojnie światowej nieruchomość uległa podziałowi. Kino od tej pory prowadziła odrębna firma (Kammerlichtspiele). W 1920 roku salę kinową powiększono kosztem sceny, którą rozebrano. Od tej pory na obu kondygnacjach było łącznie 566 siedzących miejsc. W tym samym czasie Klein cieszył się emeryturą, a hotelem i restauracją zarządzał dzierżawca. W 1921 roku przebudowano parter - zlikwidowano arkady, a w jednym z pomieszczeń zaczął swoją działalność samochodowy salon wystawowy. W 1927 roku pomieszczenie znajdujące się pomiędzy kinem a restauracją przebudowano na piwiarnie, którą nazwano "Pommernstube" (Izba Pomorska). Po 1945 roku hotel przemianowano na "Centralny", restaurację na "Centralną", a kino na "Polonia". W 1947 roku hotel wraz z restauracją prowadził Jan Wielandt ze wspólnikami. W latach 60. nazwę hotelu przemianowano na "Gryf", a do tego ulokowano tu dyrekcję miejskich hoteli. W 1975 roku wykonano remont elewacji, a z czasem przeprowadzono remont restauracji "Staromiejska". Po remoncie lokalem kierował Andrzej Ślebioda, który z czasem założył spółkę z Władysławem Piotrowiczem i "Staromiejska" przeistoczyła się w restaurację węgierską. W tym czasie hotelowi przyznano trzy gwiazdki, a przenocować mogło tu jednorazowo 77 osób. W 2011 roku dotychczasowy właściciel, spółka Przymorze sprzedała prywatnemu przedsiębiorcy restaurację i hotel "Staromiejski". Obecnie w budynku działa jedynie hotel, a restauracja od kilku lat jest nieczynna.