Pas një kalvari të gjatë bisedimesh që u shtri në 12 vite, me 15 shtator 1987 u nënshkrua Protokolli i Bisedimeve për vendosjen e marrëdhënieve diplomatike midis Shqipërisë dhe Republikës Federale Gjermane, e njohur ndryshe në atë kohë si Gjermania Perëndimore.

Deri në vitin 1975 midis Shqipërisë dhe RFGJ nuk pati asnjë kontakt zyrtar politik. Shteti shqiptar kishte refuzuar të vendoste marrëdhënie diplomatike me shtetin gjermano perëndimor kur ai u krijua në 1949 dhe po kështu edhe kur Shqipëria doli nga blloku sovjetik në 1961.

Qeveria e koalicionit CDU-SDP që erdhi në pushtet në 1966, me kancelar Kurt Kiesinger, me iniciativën e Ministrit të Jashtëm të saj Willy Brandt, ndërmori një fushatë pajtimi e vendosjeje të marrëdhënieve diplomatike me vendet e Evropës Lindore, e njohur ndryshe si Ostpolitika. Kjo filozofi e politikës së jashtme gjermano perëndimore u zhvillua më fuqishëm kur këtë qeveri e drejtoi Willy Brandt tashmë në postin e Kancelarit (1969-1974). Në 1971 Brandt i’u dha Çmimi Nobël për Paqen për përpjekjet e tij për të arritur pajtimin me Evropën Lindore.

Në këtë kuadër, përçapje për normalizimin dhe vendosjen e marrëdhënieve diplomatike u bënë edhe pranë Tiranës zyrtare nëpërmjet përfaqësuesve të saj në Vjenë, Beograd e Paris. Problem i mbetur pezull ndërmjet dy qeverive ishte trajtimi i çështjes së pagesës së dëmshpërblimeve të Luftës së Dytë Botërore. Sipas vendimeve të Konferencës së Parisit për Dëmshpërblimet në 1946, RFGJ si trashëgimtare e zonave perëndimore të pushtimit të Gjermanisë u ngarkua të paguante dëmshpërblime për dëmet e shkaktuara gjatë Luftës së Dytë Botërore për 18 shtete, ndër to edhe Shqipëria. RFGJ refuzonte pagesën e tyre, bazuar në Marrëveshjen e Londrës 1953 e cila e shtynte zgjidhjen e këtij problemi pas nënshkrimit të Traktatit të Paqes me Gjermaninë.

Kërkesën e qeverisë shqiptare për pagesën e dëmshpërblimeve bashkë me listën e gjatë të dëmeve të shkaktuara gjatë luftës e paraqiti Ministri i Jashtëm Nesti Nase më 28 shtator 1973 në Asamblenë e Përgjithshme të OKB-se, pikërisht në vitin kur Fuqitë e Mëdha kishin rënë dakord që të dy Gjermanitë të pranoheshin si anëtare me të drejta të plota në OKB. Pavarësisht qëndrimit të prerë të shtetit shqiptar, gjermano perëndimorët nuk hoqën dorë nga synimi i tyre për të vendosur marrëdhënie diplomatike me Shqipërinë, pasi ajo ishte shteti i fundit lindor me të cilën nuk kishte të vendosura këto marrëdhënie.

Më 28 qershor 1975 në ambasadën gjermane në Beograd u dërgua kërkesa zyrtare e palës shqiptare për pagesën e dëmshpërblimeve e cila do i dorëzohej ambasadës së RFGJ atje. Kjo shënoi edhe pikënisjen e një rruge të gjatë bisedimesh për 12 vite, debate e shumë kontakte midis diplomatëve e ekspertëve nga të dy palët në Beograd e më pas në Vjenë dhe në Bon. Qëllimi ishte gjetja e një kompromisi për pagesën e dëmshpërblimeve që ti hapej rrugë normalizimit dhe vendosjes së marrëdhënieve diplomatike midis dy shteteve. Pala gjermane këmbëngulte që në fillim të vendoseshin marrëdhëniet diplomatike pasi kështu do të krijoheshin kushtet për zgjidhjen e çështjeve ekonomike e financiare. Ky proces i gjatë u ndihmua edhe nga tre vizitat “private” të kryeministrit të Bavarisë Franz Josef Strauss, të shoqëruara me oferta të mira ekonomike në periudhën 1984-1987.

Në kushtet e krizës së thellë ekonomike të viteve ‘80-të si pasojë e vetë izolimit të Shqipërisë në marrëdhëniet me jashtë, dhe në kuadër të përpjekjeve të filluara pas vitit 1985 për zbutje “të kujdesshme” të tensioneve të krijuara në politikën e jashtme, më 15 shtator 1987 u nënshkrua në Tiranë Protokolli i bisedimeve për vendosjen e marrëdhënieve diplomatike midis RFGJ dhe Shqipërisë . Shpallja zyrtare e vendosjes së këtyre marrëdhënieve u bë njëkohësisht në Tiranë e Bon më 2 tetor 1987. Ky moment u shoqërua në një kohë të shkurtër me nënshkrimin e Protokollit të Bashkëpunimit Ekonomik e Tekniko-Shkencor midis dy vendeve, nga i cili Shqipëria përfitonte një mbështetje të madhe në pajisje e mjete financiare për ekonominë e saj.