Με νέα ιδιοκτησία, τον τότε πρόεδρο της ποδοσφαιρικής ομάδας Γιώργο Μπατατούδη, ρόστερ εκατοντάδων εκατομμυρίων (Λιαδέλης, Σιγάλας, Κορωνιός, Κολντεμπέλα), αρχηγό πλέον το Γιάννη Γιαννούλη, προπονητή ξανά τον Κώστα Φλεβαράκη (με τον οποίο είχε κατακτήσει το Κύπελλο του ΄99) και πολλά όνειρα ο ΠΑΟΚ ξεκινά τη σεζόν 2000-01 για να κατακτήσει και την Ευρώπη, αλλά μένει από… βενζίνη πολύ γρήγορα και το όνειρο γίνεται εφιάλτης.

Την ίδια τύχη θα έχουν όλες οι προσπάθειες που ακολούθησαν. Η πορεία προς την ειδική εκκαθάριση είναι μία κακή ανάμνηση για όλους. Η ομάδα περνά πολύ δύσκολες στιγμές, με τεράστια οικονομικά προβλήματα και από την αρχή της περιόδου 2001-02 έχει διοίκηση διορισμένη από το Πρωτοδικείο και πρόεδρο τον Βασίλη Οικονομίδη, που ξεκινά τη σεζόν με προπονητή το Λευτέρη Σούμποτιτς και την ολοκληρώνει με τον Βαγγέλη Αλεξανδρή. Η ειδική εκκαθάριση δίνει στον ΠΑΟΚ τη δυνατότητα να ξεκινήσει και πάλι από την αρχή κι αυτό ακριβώς γίνεται… Βασιζόμενος στα νέα του παιδιά (Βασιλειάδης, Βασιλόπουλος, Μαυροκεφαλίδης), με προπονητή πλέον τον Μπάνε Πρέλεβιτς και από τις 17 Ιανουαρίου 2004 τον Τάκη Πανελούδη στην ιδιοκτησία της νέας ΚΑΕ, ο ΠΑΟΚ ξεκινά και πάλι από την αρχή. Η προσπάθεια δεν ολοκληρώνεται όπως θα περίμενε κανείς και κυρίως οι φίλαθλοι της ομάδας που στήριξαν όπως πάντα το νέο ξεκίνημα.