De letters PAOK staan voor Panthessalonikeios Athlitikos Omilos Konstantinoupoliton (Grieks: Πανθεσσαλονίκειος Αθλητικός Όμιλος Κωνσταντινουπολιτών).
PAOK is overigens geen onbekende bij de meeste voetballiefhebbers. Zo staat de club bekend om zijn zeer harde en fanatieke aanhang, die ook banden heeft met de eveneens beruchte aanhang van Partizan Belgrado (Grobari). Wedstrijden met stadgenoten Aris en Iraklis en landelijke rivaal Olympiakos Piraeus resulteren dan ook altijd in hevige rellen tussen supporters van beide ploegen en de politie. Wedstrijden tussen PAOK en Olympiakos Piraeus worden zonder uitpubliek gespeeld. PAOK werd in het verleden een aantal keren beboet door de UEFA.
Niet alleen de aanhang van de club kan het bont maken, ook de voorzitter van PAOK, Ivan Savvidis, zorgde voor chaos tijdens de wedstrijd tussen de club en AEK Athene op 11 maart2018. Nadat de scheidsrechter een doelpunt van PAOK afkeurde vanwege buitenspel, kwam Savvidis het veld op en bedreigde de arbitrage terwijl hij een pistool in een holster droeg. De wedstrijd werd gestaakt.[1]
In de nasleep van dat tumultueuze duel behaalde AEK Athene op 23 april2018 de eerste Griekse titel in 24 jaar, nadat PAOK Saloniki tevergeefs in beroep was gegaan tegen de straffen die het opgelegd had gekregen.[2] De tuchtcommissie van de Griekse voetbalbond wees AEK als reglementaire winnaar aan: 3-0. PAOK kreeg bovendien drie punten in mindering gebracht. Daarnaast moest de club een boete van 63.000 euro betalen en mocht voorzitter Savvidis zich drie jaar niet vertonen bij voetbalwedstrijden in zijn vaderland. Omdat de straffen bleven staan voor PAOK, kon de club AEK Athene niet meer achterhalen op de ranglijst.
Double
Op 21 april 2019 won PAOK na 34 jaar opnieuw het Griekse kampioenschap. Diego Biseswar maakte deel uit van dat team en scoorde ook in de kampioenswedstrijd tegen Levadiakos. Op 11 mei 2019 won PAOK de Griekse bekerfinale tegen AEK Athene met 1-0, waarmee de eerste double uit de clubgeschiedenis een feit was. En passent werd hiermee ook voor de derde maal op rij de Griekse beker gewonnen tegen dezelfde tegenstander.
Tot 2006 stond de hoogste divisie bekend als Alpha Ethniki. Het 2e niveau staat sinds 2010 bekend als Football League en sinds 2019 als Super League 2. Het 3e niveau kende van 2019-2021 de naam Football League.