PAOK FC își trage originea din Clio Sports Club, înființat de intelectuali greci, în 1877, în cartirul Pera din Constantinopole, actuala metropolă Istanbul din Turcia. 

Clubul PAOK își trage originea în actualul cartier Beyoglu din Istanbul

Cartierul, locuit încă de la înființarea orașului Byzantium (7 î.Ch.), era populat la acea vreme majoritar de etnici creștini, respectiv greci, armeni și italieni și se găsea în partea europeană a capitalei Imperiului Otoman. În 1884, clubul a fost redenumit Hermes Sport Club, iar în 1914 a fost fondată secția de fotbal, culorile ei fiind galben și negru. 

Acesta a fost redenumit Athlitikos Syllogos Peran, dar au urmat vremuri tulburi. În 1923, odată cu fondarea Republicii Turce și ridicarea unui val de naționalism, clubul a fost forțat să-și schimbe denumirea în Beyogluspor Kulubu (Beyoglu e denumirea cartierului Pera, în limba turcă). 

Turcia și Grecia, fapte rușinoase după Al Doilea Război Mondial

În urma înfrângerii Greciei de către Turcia, în încercarea de a-și recupera teritoriile istorice din Tracia și de pe litoralul Mării Egee, a urmat un val de represiuni asupra etnicilor eleni, greci pontici, armeni, cerchezi și asirieni din Turcia, speculându-se că până la 4 milioane de persoane și-au pierdut viața în acest genocid nerecunosut de statul turc. 

Grecia a răspuns la fel de sălbatic, la rândul ei, prin distrugerii ale localităților musulmane și linșaje ale etnicilor turci stabiliți pe teritoriul european. În urma presiunilor internaționale, cele două țări au semnat Tratatul de la Lausanne (iulie 1923) și au fost de acord pentru un schimb de populații, peste 1.5 milioane de greci și creștini de alte naționalități au luat drumul Greciei și peste 500.000 de turci europeni și greci musulmani au fost trimiși în Turcia. 

Refugiații din Turcia au înființat PAOK, în 1926

În 1926, refugiații greci stabiliți în portul Salonic, în Macedonia grecească, și grupați în organizația politică și socială Enosis Konstantinoupoliton Thessalonikis au înființat cluburile rivale Panthessalonikios Athlitikos Omilos Konstadinoupoliton (PAOK) și Athlitiki Enosis Konstantinoupoliton Thessalonikis (AEKT). PAOK a fost prima grupare care a permis înscrierea în rândurile sale și ale celor care nu erau originari din Constantinopole. 

AEKT a fost desființat în 1929, iar majoritatea membrilor săi s-au înscris în PAOK, prilej cu care s-a adoptat sigla actuală, cu acvila bicefală imperială bizantină. Primul meci oficial a fost contra lui Megas Alexandros Thessaloniki, o victorie cu 2-1, și echipa a debutat în prima divizie în sezonul 1930-1931. 

PAOK este mândria Macedoniei, provincia din Nordul Greciei

De atunci, clubul nu a mai retrogradat niciodată din divizia de elită a fotbalului grec, iar în palmares a acumulat patru titluri de campioană (1975-1976, 1984-1985, 2018-2019, 2023-2024), opt trofee Cupa Greciei (1971-1972, 1973-1974, 2000-2001, 2002-2003, 2016-2017, 2017-2018, 2018-2019, 2020-2021), o Cupă a Greciei Mari (1973) și șapte titluri ale Regiunii Macedonia.

În cupele europene, "alb-negrii" au ajuns în sferturile de finală ale Cupei Cupelor (1973-1974) și ale Conference League (2021-2022, 2023-2024). PAOK este cunoscută pentru fanii săi fanatici și pentru atmosfera incendiară făcută de ei pe Stadionul Toumba, pe care echipa evoluează din 1959.  

Beyogluspor funcționează încă, având secții de fotbal, volei și baschet. Secția de fotbal este înscrisă la nivel de amatori (Liga a 8-a, Ikinci Amator Kume) în campionatul Regiunii Istanbul, dar a jucat în prima divizie între 1962 și 1964.

Beyoglu este unul dintre cartierele istorice și turistice ale Istanbulului, cu o suprafață de 9 kilometri pătrați și o populație de 225.920 de locuitori, majoritar turci și kurzi. Zona cuprinde multe ambasade și școli de renume, dar și numeroase muzee, bulevardul comercial Istiklal Caddesi, Piața Taksim și galeria Cicek Pasaji.