Το τέλος της δεκαετίας του΄70 σήμανε και το τέλος των πέτρινων χρόνων για τον ΠΑΟΚ, που έδειξε από τα πρώτα χρόνια της νέας δεκαετίας ότι μπορεί να πρωταγωνιστήσει. Ήδη από την περίοδο 1980-81 κάνει την εμφάνισή του ο Παναγιώτης Φασούλας που έγινε στυλοβάτης της προσπάθειας του ΠΑΟΚ για περισσότερο από δέκα χρόνια. Το 1982 ο ΠΑΟΚ για πρώτη φορά στην ιστορία του συμμετέχει και στον τελικό του Κυπέλλου Ελλάδος και παρά το γεγονός ότι ο αγώνας διεξάγεται στη δική του έδρα, το Αλεξάνδρειο, χάνει τη μεγάλη ευκαιρία με την ήττα του (63-65) από τον Παναθηναϊκό.
Την αμέσως επόμενη χρονιά (1982-83) ο ΠΑΟΚ θα πλησιάσει για πρώτη φορά (μετά το 1959) τόσο κοντά στην κατάκτηση του τίτλου, αλλά θα μείνει στη 2η θέση, ισοβαθμώντας με τον Παναθηναϊκό και με μόλις μία νίκη λιγότερη από τον πρωταθλητή Άρη. Ο ΠΑΟΚ ήταν προφανές ότι είχε πάρει ένα δρόμο που μόνο στην κορυφή θα μπορούσε να βγάλει. Και σε αυτό, βοήθησε και μία σπουδαία μεταγραφική κίνηση, η απόκτηση του Νίκου Σταυρόπουλου από τον ΓΣ Λάρισας και με το ποσό ρεκόρ (10.000.000 δραχμές) για την εποχή.