Ο ΠΑΟΚ ταξίδεψε πρώτη φορά στη Μολδαβία για ένα ευρωπαϊκό παιχνίδι. Όμως, δεν θα είναι η πρώτη φορά απέναντι σε ομάδα που προέρχεται από το λεγόμενο πρώην ανατολικό μπλοκ. Ο Δικέφαλος έχει δώσει ματς σε χώρες όπως την πρώην Σοβιετική Ένωση, την Πολωνία, την Ουκρανία, τη Βουλγαρία, το Καζακστάν και φυσικά τη γειτονική και με πολλά κοινά χαρακτηριστικά, Ρουμανία
Η πρώτη και… άγραφη (για την ΟΥΕΦΑ) παρουσία του ΠΑΟΚ σε χώρα του πρώην ανατολικού μπλοκ ήταν τη σεζόν 1970-’71 όταν γνώρισε βαριά ήττα με 5-0 από την Ντιναμό Βουκουρεστίου για το Κύπελλο Εκθέσεων.
Δύο χρόνια αργότερα ο ΠΑΟΚ ξεκινούσε την πορεία για τους “8” του κυπέλλου Κυπελλούχων από την Πολωνία. Στο γήπεδο του στρατού (Polish Army Stadium) απέσπασε ισοπαλία 1-1 από την Λέγκια Βαρσοβίας, αν και προηγήθηκε με γκολ του Χρήστου Τερζανίδη.
Ταξιδεύοντας στο Κίεβο τον Οκτώβριο του 1976 ο “Δικέφαλος” γνώριζε εξ αρχής ότι θα έχει δύσκολη αποστολή απέναντι στην πανίσχυρη, τότε, πρωταθλήτρια Σοβιετικής Ενωσης, Ντιναμό Κιέβου. Αυτό επαληθεύτηκε και μέσα στο γήπεδο το βράδυ της 20ης Οκτωβρίου με το 4-0 υπέρ των Ρώσων.
Δεύτερη επίσκεψη στην Πολωνία και δεύτερο θετικό αποτέλεσμα τον Σεπτέμβριο του 1977 για το κύπελλο κυπελλούχων με την εύκολη νίκη 2-0 επί της Ζαγκλέμπιε σ’ ένα ματς που αγωνίστηκε ο Αγγελος Αναστασιάδης, ο οποίος σκόραρε με πέναλτι στη ρεβάνς της Τούμπας (2-0).
Ο ΠΑΟΚ επισκέφτηκε την γειτονική Βουλγαρία και το Πλόβντιβ για να αντιμετωπίσει τον Σεπτέμβριο του 1983 την Λοκομοτίβ στα πλαίσια του α’ γύρου του κυπέλλου ΟΥΕΦΑ. Το εμπόδιο αποδείχθηκε εύκολο, καθώς με γκολ των Δημόπουλου και Γεωργόπουλου νίκησε 2-1 και σφράγισε την πρόκριση μέσα στην Τούμπα με μια ακόμη νίκη (3-1)
Η μεγαλύτερη σε έκταση εκτός έδρας νίκη, όχι μόνο του ΠΑΟΚ, αλλά και όλων των ελληνικών ομάδων στα ευρωπαϊκά κύπελλα καταγράφηκε στην Τυφλίδα. Στις 16 Σεπτεμβρίου 1999 ο ΠΑΟΚ συνέτριψε με 7-0 την Λοκομοτίβ Τυφλίδας, πετυχαίνοντας τα επτά γκολ μέχρι το 69ο λεπτό.
Ο “Δικέφαλος” επισκέφτηκε δύο φορές, μέσα σ’ ένα μήνα, την Ουκρανία το φθινόπωρο του 2005. Αρχικά πήρε μια παλικαρίσια πρόκριση επί της Μέταλιστ (2-2) τελειώνοντας το ματς με εννιά παίκτες και στη συνέχεια αντιμετώπισε για τη φάση των ομίλων του κυπέλλου ΟΥΕΦΑ την πανίσχυρη Σαχτάρ από την οποία ηττήθηκε 1-0 με αμφισβητούμενο πέναλτι – γκολ του Μπραντάο και τον Ραζβάν Ρατς να αγωνίζεται τότε με τη φανέλα της Σαχτάρ εναντίον του ΠΑΟΚ!
Την ίδια χρονιά θα επισκεφτεί και το Βουκουρέστι, όπου υπό καταρρακτώδη βροχή θα ηττηθεί 1-0 από την Ραπίντ.
Στο Λβιβ της Ουκρανίας ο ΠΑΟΚ σφράγισε την πρόκριση στους ομίλους του Γιουρόπα Λιγκ την περίοδο 2011-2012. Με γκολ του Σωτήρη Μπαλάφα άφησε έξω την Καρπάτι του Λούκας Πέρεθ στη ρεβάνς που είχε γίνει τον Αύγουστο του 2011 στο “Ουκράινα Στέντιουμ”.
Την ίδια χρονιά για τους ομίλους θα βρεθεί στο Καζάν και θα αποσπάσει ισοπαλία 2-2 από την Ρούμπιν. Προηγήθηκε με τον Αθανασιάδη, οι Ρώσοι απάντησαν με δύο γκολ μέσα σε 13 λεπτά στο β’ μέρος για να ισοφαρίσει ο Φωτάκης στο 81ο λεπτό.
Πέρσι για τα προκριματικά του Τσάμπιονς Λιγκ βρέθηκε για τέταρτη φορά στην Ουκρανία φέρνοντας ισοπαλία 1-1 με την Μέταλιστ στο Χάρκοβο και παίρνοντας την πρόκριση στα… χαρτιά.
Στο πιο μακρινό ταξίδι του σε χώρα του πρώην ανατολικού μπλοκ ο ΠΑΟΚ ταξίδεψε πέρσι στην Αστάνα του Καζακστάν και επικράτησε με 2-0 για τους ομίλους του Γιουρόπα Λιγκ.
