Mest kjent er likevel fotballaget, som spiller i Gresk superliga. Fotballaget ble grunnlagt i 1926 og spille sine hjemmekamper på Toumba Stadion. I 2007 var det totalt 7 % av greske fotballsupportere som heiet på PAOK. Fotballagets trener heter Răzvan Lucescu og er fra Romania.
Laget har blitt ligamestere fire ganger, i 1975-76, 1984-85, 2018-19 og 2023-24 og vunnet cupen åtte ganger, i 1971-72, 1973-74, 2000-01, 2002-03, 2016-17, 2017-18, 2018-19 og 2020-21.