Η επίσημη διαπραγματευτική διαδικασία άρχισε λίγο μετά τη διακήρυξη της ανεξαρτησίας τής μέχρι τότε Σοσιαλιστικής Δημοκρατίας της Μακεδονίας από την Ομοσπονδιακή Δημοκρατία της Γιουγκοσλαβίας στις 24 Ιανουαρίου 1991. Οι εξελίξεις τότε ήταν δραματικές καθώς η Γιουγκοσλαβία διαλύονταν και οι χώρες που την συγκροτούσαν, η μία μετά την άλλη γίνονταν ανεξάρτητες Δημοκρατίες. Πρωταγωνιστικό ρόλο διαδραμάτισε η Γερμανία η οποία σε μια δραματική συνεδρίαση των υπουργών Εξωτερικών της ΕΕ στις 16 Δεκεμβρίου 1991, πίεσε και πέτυχε τη διάλυση της Γιουγκοσλαβίας, αναγνωρίζοντας μονομερώς σε πρώτη φάση, την Κροατία, τη Σλοβενία και τα Σκόπια προς τα οποία ωστόσο έθεσαν σειρά όρων:

Τα Σκόπια εκλήθησαν να προσφέρουν συνταγματικές και πολιτικές εγγυήσεις στους γείτονές τους ότι: α) Δεν έχουν εδαφικές διεκδικήσεις, β) Δεν ασκούν εχθρική προπαγάνδα, γ) Δεν χρησιμοποιούν ονομασία που υπονοεί εδαφικές διεκδικήσεις.

Η Ελλάδα προσπάθησε και μέσω της ΕΕ και μέσω κινήσεων προς την μεγάλες χώρες, να αποτρέψει την αποδοχή της χώρας αυτής ως «Δημοκρατίας της Μακεδονίας». Διαφαίνονταν ήδη ότι η υπόθεση αυτή εξελίσσονταν σε δύσκολο διπλωματικό κεφάλαιο και για τα Βαλκάνια και για την Ευρώπη γενικότερα. Για τον λόγο αυτό, η ΕΕ άρχισε να παρεμβαίνει.

Το πακέτο Πινέιρο

Στις 15 Ιανουαρίου 1992 και σύμφωνα με τη θέση της επιτροπής Μπαντεντέρ η «Δημοκρατία της Μακεδονίας» ικανοποιεί τις προϋποθέσεις για την αναγνώρισή της από την ΕΟΚ, αλλά στις 17 Φεβρουαρίου του ιδίου έτους το Συμβούλιο Υπουργών Εξωτερικών της ΕΕ αναθέτει στον προεδρεύοντα Πορτογάλο υπουργό Εξωτερικών Ζοάο Πινέιρο την «επικίνδυνη αποστολή» να βρει λύση στο θέμα της ονομασίας της ΠΓΔΜ. Ταυτόχρονα οξύνεται η αντιπαράθεση μεταξύ Αθήνας και Σκοπίων. Στα μεν Σκόπια ετοιμάζουν κείμενο και ζητούν από τις Βρυξέλλες να αναγνωρίσουν τη «Δημοκρατία της Μακεδονίας». Την επομένη 18 Φεβρουαρίου, οι πολιτικοί αρχηγοί αποφασίζουν στην Αθήνα ότι δεν γίνεται αποδεκτή η λέξη «Μακεδονία» ή παράγωγά της.

1 Απριλίου 1992. Μέσα σε αυτό το κλίμα ο υπουργός Εξωτερικών της Πορτογαλίας, που είχε την προεδρία της ΕΕ, προτείνει συμβιβασμό Αθήνας -Σκοπίων καταθέτοντας ένα πακέτο που περιελάμβανε το όνομα «Νοβοματσεντόνια» («Νέα Μακεδονία») και προέβλεπε επίσης:

α) Συμφωνία για την επιβεβαίωση των υφιστάμενων συνόρων των δύο χωρών,

β) ρήτρα ότι τα Σκόπια θα αποκηρύξουν επεκτατικές βλέψεις εναντίον της Ελλάδας και θα αποθαρρύνουν κάθε εχθρική δραστηριότητα ή προπαγάνδα, και

γ) το όνομα «Νέα Μακεδονία» ως συμβιβαστική λύση.

Η απόρριψη της πρότασης προκάλεσε ένταση εντός της ελληνικής κυβέρνησης και τελικά οδήγησε αργότερα στην παραίτηση του Αντώνη Σαμαρά από τη θέση του υπουργού Εξωτερικών.

Δηλώσεις Πινέιρο

Έχει ιδιαίτερο πολιτικό και ιστορικό ενδιαφέρον πώς αποτίμησε την αποστολή του και την αποτυχία εξεύρεσης λύσης, ο ίδιος ο Πινέιρο χρόνια αργότερα, καθώς η πρότασή του απασχολεί ακόμη και σήμερα διπλωμάτες, πολιτικούς και ιστορικούς.

Σε δήλωσή του, στις 16 Νοεμβρίου 2004 στον ραδιοφωνικό σταθμό της Θεσσαλονίκης Alpha 96.5, ο Πορτογάλος πολιτικός σημείωσε: «Εκείνη την εποχή προσπαθούσαμε να έχουμε ένα πακέτο, στο οποίο το όνομα (Νέα Μακεδονία) θα πήγαινε μαζί με μία δέσμη συγκεκριμένων μέτρων. [...] Ήταν πολύ δύσκολες οι διαπραγματεύσεις γιατί εκείνη την περίοδο, ειδικά στην Ελλάδα, γινόταν μεγάλη κουβέντα για τη χρήση της λέξης Μακεδονία. Εκείνη την εποχή λοιπόν προτείναμε ότι ο όρος θα μπορούσε τελικά να χρησιμοποιηθεί, μαζί όμως με ένα πακέτο, στο οποίο η σύνδεση της χρήσης του ονόματος και των σχέσεων της ΕΕ θα περνούσε μέσα από την Ελλάδα».

Στην ερώτηση για το εάν ο Αντώνης Σαμαράς και ο Κωνσταντίνος Μητσοτάκης είχαν διαφορετική αντίληψη για το χειρισμό του ζητήματος σημείωσε ότι αρχικά διατύπωναν διαφορετικές θέσεις, ωστόσο, στο τέλος είχαν και οι δύο την ίδια θέση.

Σε άλλες δηλώσεις του, στην εφημερίδα Καθημερινή στις 23 Δεκεμβρίου 2007, ο Πινέιρο, απαντώντας σε ερώτηση αν κάτι ανάλογο με το "πακέτο Πινέιρο" θα ήταν δυνατόν τώρα, με αρκετή διορατικότητα απάντησε:

«Πιστεύω ότι πρέπει βέβαια να υπάρξουν προσαρμογές, όμως αν η ΠΓΔΜ θέλει να "ενσωματωθεί", εντός εισαγωγικών, στην Ευρώπη τότε θα πρέπει να κάνουν παραχωρήσεις. Αν η Ελλάδα θέλει να διαδραματίσει ρόλο, σταθεροποιητικό ρόλο στην περιοχή τότε θα πρέπει και αυτή να κάνει παραχωρήσεις. Έτσι ίσως το "πακέτο" μπορεί να επανέλθει, με τροποποιήσεις».

Η επόμενη φάση

Οι διαπραγματεύσεις και οι προσπάθειες για την εξεύρεση λύσης συνεχίζονται. Τον Ιανουάριο του 1993, τρεις ευρωπαϊκές χώρες, το Ηνωμένο Βασίλειο, η Γαλλία και η Ισπανία, προτείνουν συμβιβαστική επίλυση του θέματος για την ονομασία της ΠΓΔΜ, με μέτρα «οικοδόμησης εμπιστοσύνης πλην ονόματος». Την πρωτοβουλία αυτή απορρίπτει η ΠΓΔΜ, ενώ ο τότε Πρόεδρός της, Κίρο Γκλιγκόροφ, θεωρεί αστεία την πρόταση των τριών ευρωπαϊκών χωρών, για ένταξη της Δημοκρατίας του στον ΟΗΕ με το όνομα FYROM (Πρώην Γιουγκοσλαβική Δημοκρατία της Μακεδονίας).

Πάντως στις 25 Μαρτίου 1993 η Αθήνα δηλώνει ότι η ΠΓΔΜ αποδέχθηκε σχέδιο απόφασης του ΟΗΕ, που προβλέπει διαδικασία επίλυσης του ζητήματος της ονομασίας του γειτονικού κράτους, υπό τους Όουεν και Βανς (πρώην υπουργοί Εξωτερικών Μεγάλης Βρετανίας και ΗΠΑ, αντίστοιχα). Η πρόταση αυτή προέβλεπε την υιοθέτηση Μέτρων Οικοδόμησης Εμπιστοσύνης (ΜΟΕ), τη διαιτησία για το οριστικό όνομα και την ένταξη της δημοκρατίας αυτής στον ΟΗΕ υπό το προσωρινό όνομα ΠΓΔΜ.

Έτσι, λίγες ημέρες αργότερα στις 7 Απριλίου με την απόφαση 817 του Συμβουλίου Ασφαλείας, η ΠΓΔΜ γίνεται δεκτή στον ΟΗΕ χωρίς σημαία και με το όνομα Πρώην Γιουγκοσλαβική Δημοκρατία της Μακεδονίας (ΠΓΔΜ , FYROM στα αγγλικά).

Λίγο αργότερα, στις 14 Μαΐου του ιδίου έτους, οι διαμεσολαβητές Βανς και Όουεν προτείνουν την ονομασία «Νέα Μακεδονία».

Και η πρωτοβουλία αυτή απέτυχε καθώς στις 28 Μαΐου η ελληνική κυβέρνηση, δια του πρέσβη Γιώργου Παπούλια, δημοσιοποιεί την άρνησή της στην πρόταση Βανς- Όουεν για το ζήτημα της ΠΓΔΜ, επειδή δεν επιτεύχθηκε συμφωνία στο θέμα της ονομασίας. Δύο ημέρες αργότερα απορρίπτεται και από τα Σκόπια.

Πολλές φορές διακινούνταν πληροφορίες για παρασκηνιακές πρωτοβουλίες της Σερβίας, που επίσημα τουλάχιστον δεν επιβεβαιώθηκαν αλλά και δεν διαψεύστηκαν. Στις 4 Ιουνίου 1993 γίνεται γνωστό ότι ο τότε πρόεδρος της ΠΓΔΜ, Κίρο Γκλιγκόροφ, απορρίπτει παρέμβαση ή πρωτοβουλία του τότε Σέρβου ηγέτη Σλόμπονταν Μιλόσεβιτς να ονομαστεί η ΠΓΔΜ «Σλαβομακεδονία».

Επανέρχεται ο Βανς

Στις 10 Μαρτίου 1994 ο Σάιρους Βανς αναπτύσσει έντονη κινητικότητα στη Γενεύη με τους υπουργούς Εξωτερικών Ελλάδας και ΠΓΔΜ. Εκεί, ο Βανς εμφανίζεται με ένα νέο κείμενο συμφωνίας, που όμως περιλαμβάνει πολλά στοιχεία από το σχέδιο του 1993 που είχε απορριφθεί.

Οι διεργασίες συνεχίζονται, με τον Βανς να μεταφέρει την έδρα των συνομιλιών στη Νέα Υόρκη όπου πραγματοποιούνται συνεχείς επαφές από 11-13 Ιουλίου 1994 με τους υπουργούς Εξωτερικών Κάρολο Παπούλια και Στέβο Τσερβενκόφσκι, παρουσία και του απεσταλμένου του Λευκού Οίκου Μάθιου Νίμιτς.

Ταυτόχρονα όμως στην Ευρώπη συνεχίζονται οι επαφές με την εμπλοκή τρίτων χωρών.

Στις 12 Ιουλίου οι υπουργοί Εξωτερικών Γερμανίας και Γαλλίας, Κλάους Κίνκελ και Αλέν Ζιπέ, προτείνουν με επιστολή τους προς τον Κάρολο Παπούλια την έναρξη διαπραγματεύσεων για την ονομασία. Η ελληνική κυβέρνηση διατυπώνει επιφυλάξεις, αλλά τελικά αποδέχεται την πρόταση και σημειώνει ότι ταυτόχρονα βρίσκεται σε εξέλιξη η πρωτοβουλία του μεσολαβητή του ΟΗΕ Σάιρους Βανς.

Έρχεται το φθινόπωρο του 1994 και οι διεργασίες εντείνονται σε όλα τα επίπεδα. Πρωτοβουλία έχει αναλάβει και το Βερολίνο μέσω του ΥΠΕΞ Κλάους Κίνκελ που προτείνει, στις 3 Οκτωβρίου, γεωγραφικό προσδιορισμό στην ονομασία (Άνω ή Νέα Μακεδονία), κάτι που ο Γκλιγκόροφ απορρίπτει, αλλά όλα δείχνουν ότι επίκεινται εξελίξεις. Την επομένη ο Γκλιγκόροφ αποδέχεται αλλαγές στο Σύνταγμα και τη σημαία με αντάλλαγμα την άρση του ελληνικού εμπάργκο.

Ωστόσο ένα μήνα αργότερα οι διαπραγματεύσεις ναυαγούν με τα Σκόπια να υπαναχωρούν στα θέματα των συμβόλων και της αλλαγής συντάγματος

Η Ενδιάμεση Συμφωνία

Από τα μέσα του 1995 άρχισε να διαφαίνεται η προοπτική επίτευξης μιας συμφωνίας μεταξύ Ελλάδας και ΠΓΔΜ που τελικά, μετά από έντονες διεργασίες και την έντονη εμπλοκή των Ηνωμένων Πολιτειών επιτεύχθηκε.

Λόγω της αδυναμίας να υπάρξει μια οριστική και άμεσα εφαρμόσιμη συμφωνία, επιτεύχθηκε η Ενδιάμεση Συμφωνία (Interim Accord) που υπογράφηκε στη Νέα Υόρκη στις 13 Σεπτεμβρίου 1995 από τους υπουργούς Εξωτερικών Παπούλια και Τσερβενκόφσκι.

Η συμφωνία που υπογράφεται σήμερα, είναι η οριστική.

Σύμφωνα με τις προβλέψεις της Ενδιάμεσης Συμφωνίας, η Ελλάδα και η ΠΓΔΜ διατυπώνουν την προσήλωσή τους στον Καταστατικό Χάρτη του ΟΗΕ σχετικά με τη διατήρηση της περιφερειακής ειρήνης, του σεβασμού της ισχύουσας μεθοριακής γραμμής, και την αποχή από πράξεις βίας και αμοιβαίων παρεμβάσεων στις εσωτερικές τους υποθέσεις.

Συμφώνησαν επίσης, να προωθήσουν μια σειρά ζητημάτων, προκειμένου να βελτιώσουν το κλίμα μεταξύ των δύο χωρών και να βελτιστοποιήσουν τη διμερή συνεργασία.

Στα άρθρα 1-8 γίνονταν μνεία σε σειρά Μέτρων Οικοδόμησης Εμπιστοσύνης (ΜΟΕ) μεταξύ των δύο χωρών. Επίσης, σύμφωνα με το άρθρο 5, οι δύο χώρες αναλάμβαναν την υποχρέωση να συνεχίσουν τις διαπραγματεύσεις με στόχο την εξεύρεση βιώσιμης λύσης στο επίμαχο ζήτημα του ονόματος.

Μετά από μια περίοδο ύφεσης στις διμερείς σχέσεις, προτάσεις και ιδέες για την επίλυση της εκκρεμότητας της ονομασίας επανέρχονταν.

Ενόψει της συνόδου κορυφής του ΝΑΤΟ το 2008 στο Βουκουρέστι, αναπτύχθηκε έντονη κινητικότητα

Η τελευταία πράξη

Στις 19 Φεβρουαρίου 2008 ο ειδικός μεσολαβητής του ΟΗΕ, Μάθιου Νίμιτς, καταθέτει συμβιβαστική πρόταση με σύνθετη ονομασία, κατά τις διαπραγματεύσεις στο ελληνικό υπουργείο Εξωτερικών. Την επόμενη ημέρα η Ντόρα Μπακογιάννη ενημερώνει τους πολιτικούς αρχηγούς. Η πρόταση αυτή δεν έχει δοθεί επίσημα στη δημοσιότητα αλλά στοιχεία της διέρρευσαν στον Τύπο.

Οι πληροφορίες γύρω από την πρωτοβουλία αυτή και την πολιτική τής τότε κυβέρνησης εξακολουθούν να αποτελούν αντικείμενο αντιπαράθεσης μεταξύ της σημερινής κυβέρνησης και της ΝΔ. Σε κάθε περίπτωση, η ελληνική θέση τροποποιήθηκε σε σχέση με την απόφαση των πολιτικών αρχηγών του 1992, με τη σύμφωνη γνώμη των περισσότερων κομμάτων και συμπυκνώνεται στην ακόλουθη: σύνθετη ονομασία της ΠΓΔΜ με γεωγραφικό προσδιορισμό που θα ισχύει έναντι όλων και με παράλληλη τροποποίηση του συντάγματος για την αντιμετώπιση του αλυτρωτισμού.

Τελικά δεν υπήρξε συμφωνία. Τα επόμενα χρόνια δεν υπήρξαν ουσιαστικές διαπραγματεύσεις εξαιτίας της άκαμπτης στάσης του πρώην πρωθυπουργού Γκρούεφσκι.

Η εκλογή του Ζόραν Ζάεφ στην πρωθυπουργία το 2017 αποτέλεσε την αρχή για αλλαγή της στάσης της ΠΓΔΜ που έθεσε ως στρατηγικό στόχο την ένταξη της χώρας του στην ΕΕ και το ΝΑΤΟ. Από τις αρχές του 2018 άρχισε να αναπτύσσεται έντονη κινητικότητα με την άμεση εμπλοκή του Μάθιου Νίμιτς, την παρασκηνιακή αλλά και δημόσια στήριξη των προσπαθειών από όλες σχεδόν τις κυβερνήσεις της Ευρώπης και τις ΗΠΑ που οδήγησαν στη σημερινή υπογραφή της οριστικής συμφωνίας Ελλάδας -Βόρειας Μακεδονίας.