1926–1939: Τα πρώτα χρόνια
Μετά από δύο μήνες προετοιμασίας από την ίδρυση του συλλόγου, αποφασίστηκε ότι η ομάδα θα πρέπει να αγωνιστεί με τις υπόλοιπες ομάδες της Θεσσαλονίκης, ως μέλος της Ε.Π.Σ.Μ. Ο πρώτος αγώνας του συλλόγου ήταν μια νίκη εναντίον του Ηρακλή στις 26 Ιουλίου 1926 με σκορ 2–1. Το όραμα των ιδρυτών του συλλόγου και το σύνολο της κοινότητας του ΠΑΟΚ για τη θέσπιση έδρας, έγινε μετά από μεγάλη προσπάθεια πραγματικότητα το 1928. Έτσι στις 12 Δεκεμβρίου του 1930 εγκαινιάστηκε η έδρα του ΠΑΟΚ, το γήπεδο του Συντριβανίου. Ακολούθησε φιλικό παιχνίδι με αντίπαλο τον Άρη όπου ο ΠΑΟΚ κέρδισε με σκορ 2–1. Το γήπεδο αυτό υπήρξε έδρα του ΠΑΟΚ ως το 1959. Σήμερα στη θέση του βρίσκεται η Θεολογική Σχολή του Αριστοτελείου Πανεπιστημίου.
Κατά τη διάρκεια του ελληνοϊταλικού πολέμου 1940–41, ο ΠΑΟΚ έχασε δύο ποδοσφαιριστές του που έπεσαν για την πατρίδα στα βουνά τηςΑλβανίας. Επρόκειτο για τον τερματοφύλακα της ομάδας Νίκο Σωτηριάδη(ο πρώτος παίκτης του ΠΑΟΚ που χρίστηκε διεθνής αγωνιζόμενος το 1938 σε επίσημο αγώνα της Εθνικής Ελλάδας), καθώς και τον αμυντικό Γιώργο Βατίκη.Το πρώτο επαγγελματικό συμβόλαιο που υπογράφτηκε στον ΠΑΟΚ, αφορούσε στον εβραϊκής καταγωγής Γάλλο ποδοσφαιριστή Ραϊμόν Ετιέν (5 Σεπτεμβρίου 1928). Το συμβόλαιο προέβλεπε ότι ο ποδοσφαιριστής, προερχόμενος από τον ελληνικό σύλλογο Πέρα Κλουμπ τηςΚωνσταντινούπολης, θα λάμβανε μισθό 4.000 δραχμών το μήνα. Ο πρώτος προπονητής του ΠΑΟΚ υπήρξε το 1926, άμισθος, ο Κώστας Ανδρεάδης, ενώ πρώτος ξένος προπονητής στην ιστορία της ομάδας ήταν ο Γερμανός Ρούντολφ Γκάσνερ, ο οποίος υπηρέτησε τον ΠΑΟΚ την περίοδο 1931–32.
1946–1959: Η καταξίωση
Μετά τον Β' Παγκόσμιο Πόλεμο και την Κατοχή, στις αρχές της δεκαετίας του '50, αρχίζουν να γράφονται οι χρυσές σελίδες της ιστορίας του ΠΑΟΚ. Δημιουργούνται τα περίφημα «τσικό του Βίλλυ», του Αυστριακού προπονητή Βίλχελμ Σβέτσιγκ, από τα οποία ξεπήδησαν μεγάλα ονόματα που άφησαν εποχή (Συμεωνίδης, Γιαννέλος, Μαργαρίτης, Χαβανίδης κλπ.)
Το καλοκαίρι του 1952 πραγματοποιήθηκε ο πρώτος νυχτερινός αγώνας στο γήπεδο του Συντριβανίου ανάμεσα στον ΠΑΟΚ και στον Πανιώνιο, εγκαινιάζοντας μ' αυτόν τον τρόπο τους προβολείς που είχαν τοποθετηθεί στο γήπεδο. Ήταν το δεύτερο γήπεδο της Ελλάδας μετά από αυτό της Λεωφόρου Αλεξάνδρας που απέκτησε ηλεκτροφωτισμό.
Το 1953 σηματοδότησε την έναρξη της χρυσής εποχής του ΠΑΟΚ. Κατά τη διάρκεια των μεταγραφών του καλοκαιριού στην ομάδα ήρθαν οι Κουϊρουκίδης, Πετρίδης, Πρόγιος, Γερούδης, Κεμανίδης, Χασιώτης και Αγγελίδης. Ο ΠΑΟΚ έγινε παντοδύναμος, κερδίζοντας το πρωτάθλημα Θεσσαλονίκης για τρία συνεχόμενα χρόνια και αγωνίστηκε στις τελικές φάσεις των Πανελληνίων Πρωταθλημάτων.
Η απόκτηση του Λάμπη Κουϊρουκίδη από την Δόξα Δράμας αποτελεί την μεγάλη κίνηση για τη διοίκηση του ΠΑΟΚ. Μαζί με τους Λευτέρη Παπαδάκη και Χριστόφορο Γιεντζή θα δημιουργηθεί η ξακουστή επιθετική τριπλέτα και η τριετία 1953 – 1956 αποτελεί την πρώτη χρυσή εποχή του συλλόγου.
1959–1969: H καθιέρωση
Το 1959 ο ΠΑΟΚ γυρίζει σελίδα στην ιστορία του, καθώς αποκτά νέα έδρα, το γήπεδο της Τούμπας. Κατά τη δεκαετία του '60 ο ΠΑΟΚ προσπαθώντας να βρει το δρόμο του στη νέα δομή του ελληνικού ποδοσφαίρου, δεν κινήθηκε σε υψηλά στάνταρ. Ωστόσο οι βάσεις για τη δημιουργία της πολύ μεγάλης ομάδας άρχισαν να μπαίνουν στα τέλη της αυτής της δεκαετίας. Ο Γιώργος Κούδας, ένα από τα μεγαλύτερα ταλέντα του ελληνικού ποδοσφαίρου, επέστρεψε στην ομάδα το 1966 και σιγά - σιγά άρχισε να δημιουργείται μέσα κι από μεταγραφές σπουδαίων νεαρών Ελλήνων ποδοσφαιριστών. Ο Σταύρος Σαράφης, πρώτος σκόρερ στην ιστορία του συλλόγου με 136 γκολ, αποκτήθηκε από την Αναγέννηση Επανωμής το καλοκαίρι του 1968. Τον επόμενο χρόνο εντάσσονται στο δυναμικό του ΠΑΟΚ και οι Τερζανίδης, Παρίδης, Ασλανίδης και η μεγάλη ομάδα άρχισε να δημιουργείται. Είναι χαρακτηριστικό ότι σχεδόν όλο το οικοδόμημα του ΠΑΟΚ βασίστηκε σε Θεσσαλονικείς και Βορειοελλαδίτες ποδοσφαιριστές.
1970–1979: Η χρυσή δεκαετία
Με το σύνολο που έχτισε ο ΠΑΟΚ, κατάφερε να χτυπήσει τις παραδοσιακές ποδοσφαιρικές δυνάμεις της Αθήνας και κατέκτησε δύο κύπελλα το 1972 και το 1974 και ένα πρωτάθλημα το 1976, ενώ θα μπορούσε να κατακτήσει ακόμα περισσότερα τρόπαια, αν οι καταστάσεις ήταν διαφορετικές. Εξάλλου από το 1970 μέχρι και το 1974 ο Δικέφαλος αγωνίστηκε σε πέντε συνεχόμενους τελικούς κυπέλλου Ελλάδας. Καθοριστική για την εκτίναξη προς στις επιτυχίες υπήρξε η άφιξη του Άγγλου προπονητή Λες Σάνον το 1971. Ο Σάνον θα αποχωρήσει από την ομάδα στις 11 Οκτωβρίου 1974 και δύο μήνες αργότερα θα αναλάβει την τεχνική ηγεσία ο Ούγγρος Γκιούλα Λόραντ, υπό την καθοδήγηση του οποίου ο ΠΑΟΚ κατέκτησε το πρώτο του πρωτάθλημα το 1976 με 21 νίκες, 7 ισοπαλίες και μόλις 2 ήττες, έχοντας την καλύτερη επίθεση και άμυνα (60–17 τέρματα). Βασική ενδεκάδα: 4-4-2 με ρόμβο: Τερματοφύλακας: (1) Μλάντεν Φορτούλα, Δεξί Μπακ: (2) Γιάννης Γούναρης, Κεντρικός Στόπερ (3) Αρίσταρχος Φουντουκίδης, Κεντρικός Στόπερ (5) Φιλώτας Πέλλιος, Αμυντικό Χαφ (9) Κούλης Αποστολίδης, Δεξί Χαφ (6) Χρήστος Τερζανίδης, Αριστερό Χαφ (8) Σταύρος Σαράφης, Κεντρικός Χαφ (10) Γιώργος Κούδας, Δεξί Εξτρέμ (11) Νέτο Γκουερίνο, Αριστερό Εξτρέμ (7) Παναγιώτης Κερμανίδης.
Ανάλογα με το παιχνίδι ο Λόραντ έπαιζε και 4-5-1 (π.χ. με τον Ολυμπιακό 0-4), όπου περνούσε στα χαφ ο Άγγελος Αναστασιάδης, στη θέση του Γκουερίνο, και έπαιζε σέντερ φορ ο Κερμανίδης. Στις αρχές του πρωταθλήματος έπαιξε και ο Αχιλλέας Ασλανίδης, συνήθως δεξί εξτρέμ, ενώ ο βασικός αριστερός εξτρέμ των προηγούμενων ετών Δημήτρης Παρίδης, εναλλάσσονταν στον πάγκο και στην κερκίδα λόγω αντιεπαγγελματικής συμπεριφοράς, σύμφωνα με το Λόραντ...
1979 έως σήμερα: Η περίοδος του επαγγελματισμού
Η δεκαετία του '90 σημαδεύτηκε από την κόντρα του τότε προέδρου της ομάδας Θωμά Βουλινού με τους οργανωμένους φιλάθλους και θα οδηγήσει στις αρχές του 1996 στην αλλαγή του ιδιοκτησιακού και διοικητικού καθεστώτος. Υπό τις οδηγίες του Ολλανδού προπονητή Άρι Χάαν ο ΠΑΟΚ την περίοδο 1994–95 τερμάτισε στην 3η θέση του πρωταθλήματος και εξέτισε την ποινή αποκλεισμού από τις ευρωπαϊκές διοργανώσεις, ποινή που του είχε επιβληθεί από την ΟΥΕΦΑ το 1992 για τα επεισόδια στον αγώνα με την Παρί Σεν Ζερμέν.Η πολύ καλή αγωνιστική πορεία συνεχίστηκε και τη δεκαετία του '80, με λίγες αποτυχημένες χρονιές. Και πάλι η ομάδα κατάφερε να φτάσει σε τρεις τελικούς κυπέλλου Ελλάδας χωρίς όμως να καταφέρει να κερδίσει το τρόπαιο. Το 1984 νέοι παράγοντες στην ΠΑΕ εμπιστεύονται τις τύχες της ομάδας στον Αυστριακό Βάλτερ Σκότσικ, ο οποίος δημιουργεί ένα αξιόμαχο σύνολο. Ο ΠΑΟΚ κατακτά το 1985 το δεύτερο Πρωτάθλημα Ελλάδας και το πρώτο επαγγελματικό με απολογισμό 19 νίκες, 8 ισοπαλίες και 3 ήττες (54–26 τέρματα).
Η απόκτηση από την Ξάνθη του Ζήση Βρύζα το καλοκαίρι του 1996 και οι μεταγραφές του Κώστα Φραντζέσκου από τον ΟΦΗ και του Σπύρου Μαραγκού από τον Παναθηναϊκό τον Ιανουάριο του 1997 άλλαξαν τον αγωνιστικό προσανατολισμό της ομάδας και με προπονητή τον Άγγελο Αναστασιάδη ο ΠΑΟΚ πραγματοποιεί δύο εξαιρετικές σεζόν (1996–97, 1997–98), όπου θα εξασφαλίσει εύκολα την συμμετοχή στο κύπελλο ΟΥΕΦΑ.
Τη διετία 2001 και 2003 ο ΠΑΟΚ κέρδισε μετά από πολλά χρόνια άλλα δύο τρόπαια του κυπέλλου Ελλάδας, με νίκες επί των Ολυμπιακού (4–2) και Άρη (1–0) αντίστοιχα.
Το καλοκαίρι του 2007 ο Θοδωρής Ζαγοράκης που μόλις έχει εγκαταλείψει την αγωνιστική δράση, αποφασίζει να αναλάβει την προεδρία της ΠΑΕ σε μια προσπάθεια να οδηγήσει την ομάδα μακριά από το διοικητικό και οικονομικό αδιέξοδο στο οποίο είχε περιέλθει. Μία από τις πρώτες προτεραιότητές του υπήρξε η κατασκευή του νέου αθλητικού κέντρου της ομάδας στην περιοχή της Νέας Μεσημβρίας Θεσσαλονίκης.
