Οι σοβαρές περιπέτειες της διετίας 2007-09, μπήκαν οριστικά στο περιθώριο, όταν από το καλοκαίρι του 2009 ο ΠΑΟΚ, απέκτησε ξανά διοίκηση Πρωτοδικείου (αρχικά με τον Μιλτιάδη Κανώτα σε ρόλο προέδρου), με το Νίκο Σταυρόπουλο να ηγείται της νέας προσπάθειας από τη θέση του τεχνικού διευθυντή και να επιλέγει ως προπονητή το Σούλη Μαρκόπουλο, που έναν χρόνο νωρίτερα είχε αναδειχθεί κορυφαίος προπονητής στην Ελλάδα. Σε πολύ σύντομο χρονικό διάστημα ο ΠΑΟΚ βρήκε το δρόμο του και το έκανε με τρόπο εντυπωσιακό.
Στο ξεκίνημα της σεζόν 2009-10, ο ΠΑΟΚ πέτυχε μία ιστορική νίκη επί του Άρη, με την διαφορά ρεκόρ (83-48) των 35 πόντων, που μέχρι και σήμερα αποτελεί την μεγαλύτερη στην ιστορία των αναμετρήσεων των δύο ομάδων. Και την επόμενη χρονιά, παρά το γεγονός ότι χρειάστηκε να ξεπεράσει αρκετές δύσκολες στιγμές, ο ΠΑΟΚ κατέκτησε την 3η θέση στο πρωτάθλημα και μαζί το δικαίωμα να διεκδικήσει την επιστροφή του στην Ευρωλίγκα, μέσα όμως από την εξαιρετικά δύσκολη διαδικασία των προκριματικών. Η 3η θέση του 2011, ήταν η αρχή μίας ανοδικής πορείας, αλλά αποδείχθηκε και μία αγαπημένη συνήθεια για τον ΠΑΟΚ τα επόμενα χρόνια.
