PAOK získal dvakrát titul mistra řecké ligy - v letech 1976 a 1985 - a čtyřikrát vyhrál pohár. Největšího úspěchu na evropské scéně dosáhl klub v sezoně 1973/74, kdy se mu pod vedením legendárního kapitána Giorgose Koudase podařilo dokráčet až do čtvrtfinále tehdejšího Poháru vítězů pohárů.
Po tučných 70. letech nastal ústup ze slávy, klub navíc upadl do dluhů. Před sedmi lety se však PAOK vrátil na evropskou scénu a znovu se vyšvihl mezi řeckou elitu. Vloni se mu podařilo doplatit dluhy a tím si zajistit větší finanční stabilitu.
V minulém ročníku řecké ligy PAOK obsadil v základní části čtvrté místo a po úspěšně zvládnutém play-off si zajistil postup do kvalifikace Ligy mistrů. Ve 3. předkole však narazil na Ajax Amsterdam a po výsledcích 1:1 a 1:2 dál nepostoupil.
Ve 4. předkole Evropské ligy pak ovšem dvakrát porazil Dinamo Tbilisi a zajistil si místo v základní skupině. V ní se poprvé představil doma proti Fiorentině, utkání však po celkem nezáživném průběhu skončilo bezbrankovou remízou.
Řeckou ligu letos PAOK začal obtěžkán odpočtem tří bodů za to, že nenastoupil do odvety semifinále poháru proti Olympiakosu. Po třech kolech jsou svěřenci srbského kouče Vladimira Iviče se čtyřmi body na šestém místě. Naposledy uhráli doma bezbrankovou remízu s týmem Xanthi.
Nastoupili přitom v sestavě: Glykos - Matos, Crespo, Tzavellas, Leovac - Cimirot (79. Thiam), Biseswar (46. Pelkas), Caňas - Campos, Kuluris (59. Athanasiadis), Rodrigues.
Mezi opory týmu se řadí reprezentační útočník Stefanos Athanasiadis, který je také kapitánem týmu, dále angolský forvard Djalma Campos nebo člen kapverdské reprezentace záložník Garry Rodrigues. Zajímavostí je, že začátkem letošního roku se prezidentem klubu stal bývalý známý slovenský rozhodčí Ľuboš Micheľ .
Samostatnou kapitolou jsou divocí soluňští fanoušci, kteří za sebou mají bohatou historii výtržností. Do Liberce se jich chystají až dva tisíce a bezpečnostní složky budou v pohotovosti.