Më 24 dhjetor 1993 u vendosën marrëdhëniet diplomatike midis Republikës së Shqipërisë dhe Republikës ish-Jugosllave të Maqedonisë (FYROM) (sot Maqedonia e Veriut).

Kërkesat e Republikës së Maqedonisë, brenda federatës jugosllave, për intensifikim të kontakteve të drejtpërdrejta me qeverinë shqiptare, erdhën duke u intensifikuar që në korrik të vitit 1991, pas pranimit të Shqipërisë si anëtare në KSBE (19 qershor 1991), veçanërisht pasi ngjarjet në Jugosllavi po shkonin drejt shkëputjes së Sllovenisë dhe Kroacisë nga federata. E ndodhur nën rrezikun e bllokimit nga fqinjët e saj, ajo i drejtoi sytë nga Shqipëria si e vetmja mundësi për të dalë në Evropë. Qeveria maqedonase, në kanale jo zyrtare i propozoi qeverisë shqiptare disa projekte bashkëpunimi në ekonomi e transport apo ftesa për takime të ministrave homologë. Po në rrugë jo-zyrtare, qeveria pluraliste shqiptare iu përgjigj palës maqedonase se edhe ajo kishte interes të intensifikonte marrëdhëniet me Republikën e Maqedonisë, por gjithçka do të varej në një masë të madhe nga qëndrimi i tyre ndaj popullsisë shqiptare në Maqedoni.

Në 8 shtator 1991 Maqedonia shpalli pavarësinë e saj nga federata jugosllave. Greqia kundërshtoi njohjen e saj ndërkombëtare për shkak të flamurit dhe emrit që konsideroheshin simbole helene.

Në 21 shkurt 1992, Ministri i Jashtëm maqedonas. Denko Maleski, njoftoi zyrtarisht ministrinë e jashtme shqiptare se Republika e Maqedonisë nuk mund të përfaqësohej më në Shqipëri nga autoritetet federative jugosllave. Derisa të përfundohej njohja e saj ndërkombëtare, ajo do të dërgonte në Shqipëri Të Ngarkuar me Punë të përkohshëm, që të mos pengohej komunikimi dhe bashkëpunimi me Shqipërinë në fushat e interesit reciprok. Ajo ftoi edhe palën shqiptare të bënte të njëjtën gjë. Maqedonia hapi në Tiranë përfaqësinë e saj konsullore me 1 gusht 1992. Edhe qeveria shqiptare dërgoi Të Ngarkuar me Punë të Përkohshëm në Shkup në fund të vitit 1992.

Ndërkohë qeveria shqiptare e lidhi njohjen e Maqedonisë dhe votën pro kërkesës së saj për tu anëtarësuar në KSBE, me qëndrimin e qeverisë maqedonase ndaj shqiptarëve që banonin atje, dhe reflektimin në Kushtetutën e re të vendit të statusit të shqiptarëve si kombësi shtet formuese si dhe të gjitha të drejtat që kërkonin parimet e KSBE dhe aktet e tjera ndërkombëtare.

Pas dakordësisë mes Maqedonisë dhe Greqisë që Maqedonia të pranohej në OKB me emrin: ish-Republika Jugosllave e Maqedonisë (FYROM), mars 1993, u shtuan edhe njohjet ndërkombëtare të Maqedonisë nga vendet e tjera evropiane duke përdorur këtë emër. Në dhjetor 1993, qeveria maqedonase, i paraqiti qeverisë shqiptare një projekt-protokoll për vendosjen e marrëdhënieve diplomatike midis dy vendeve, duke përdorur emrin Republika e Maqedonisë. Tirana zyrtare, nën presionin edhe të shteteve të tjera evropiane, u shpreh e gatshme të vendoste marrëdhënie diplomatike, por duke përdorur emrin ish-Republika Jugosllave e Maqedonisë (FYROM), deri në zgjidhjen përfundimtare të emrit. Kjo do të ndodhte me shkëmbim notash midis përfaqësuesve të dy vendeve. Pala maqedonase ra dakord.

Më 24 dhjetor 1993 në godinën e MPJ në Tiranë u shkëmbyen notat diplomatikeë me përfaqësuesin maqedonas në Tirane, për vendosjen e marrëdhënieve diplomatike në nivel ambasadorësh, dhe po atë ditë në orën 20.00 (ora lokale) ky lajm u shpall në mediat e vendit në Tiranë e Shkup. Gjate vitit 1994 u shkëmbyen edhe ambasadorët në dy kryeqytetet respektive.

Maqedonia e Veriut