Pierwszym polskim przedstawicielem dyplomatycznym, akredytowanym w Albanii był Władysław Günther-Schwarzburg, poseł polski w Atenach, który w 1937 uzyskał także akredytację na obszar Albanii. Günther-Schwarzburg reprezentował Polskę w 1938 na ślubie władcy Albanii Zoga I z ks. Geraldine Apponyi. Do 1939 nie doszło do utworzenia w Tiranie stałej polskiej misji dyplomatycznej.
Ponowne nawiązanie stosunków dyplomatycznych między Polską a Albanią nastąpiło 6 listopada 1945, w lipcu 1954 podniesiono rangę przedstawicielstw do poziomu ambasad. Do 1949 stronę polską reprezentował ambasador polski w Belgradzie, akredytowany także w Tiranie. W 1949 w Tiranie pojawił się pierwszy polski przedstawiciel dyplomatyczny – Bolesław Jeleń.
W lutym 1966 rząd Polskiej Rzeczypospolitej Ludowej uznał działalność ówczesnego ambasadora Ludowej Republiki Albanii Koço Priftiego za niezgodną z przyjętymi normami i zwyczajami międzynarodowymi, co spowodowało uznanie go za persona non grata. W ramach retorsji strona albańska wydaliła ówczesnego ambasadora w Tiranie – Stanisława Rogulskiego. Incydent ten spowodował pogorszenie stosunków polsko-albańskich i czasowe odwołanie ambasadorów, a w konsekwencji obniżenie rangi wzajemnych stosunków, trwające aż do 1990.