Початок був покладений 20.02.1938 в матчі збірних Греції та Палестини на стадіоні «Леофорос Александрас». Воротар Нікос Сотіріадіс став першим представником ПАОК в збірній нашої країни, замінивши на 15 'Спіроса Склавунос, який розпочав у стартовому складі. Це був передостанній матч грецької національної збірної перед Другою світовою війною.

У першій неофіційною товариській зустрічі після війни, 17.03.1948 в поєдинку зі збірною військово-повітряних сил брав участь Йоргос Муратідіс. 28.11.1948 Йоргос Муратідіс зіграв і в офіційному товариському матчі з Туреччиною в Стамбулі.

Далі були лише окремі виклики з борну, поки 18 червня 1971 матчі Греція - Мальта (2-0) відразу двоє футболістів ПАОК вийшли в стартовому складі. Ними стали Ставрос Сарафіс і Йоргос Гунаріс.

Кілька місяців по тому, 04.03.1972 в поєдинку Греція - Італія (2-1) футболку національної збірної одягли Сарафіс, Кудас і Парідіс. Кудас, Терзанідіс, Асланідіс і Сарафіс склали першу четвірку футболістів ПАОК, які захищали кольори збірної 31.01.1973. Той поєдинок з Болгарією завершився внічию 2-2.

У товариській зустрічі з Кіпром (2-1) 01.04.1975 «Двоголовий» представляли вже п'ять гравців: Гунаріс, Пелліос, Терзанідіс, Анастасіадіс і Парідіс.

Через кілька днів, 04.06.1975 в офіційному протистоянні на «Тумбі» повторилося досягнення в «п'ять зірок». Пелліос, Іосіфідіс, Анастасіадіс, Апостолидису і Асланідіс вийшли на поле проти Мальти (2-0) у відбірковому матчі Кубка націй 1976.

Абсолютний рекорд становив шість футболістів ПАОК в національній збірній. Такий показник був зафіксований в двох товариських зустрічах: 15.04.1981 Кіпр - Греція 0-1 (Гунаріс, Іосіфідіс, Кудас, Даманакіс, Орфаноса, Костікос) і 23.09.1981 Греція - Данія 2-3 (Пантеліс, Іосіфідіс, Костікос, Кудас, Даманакіс, Гунаріс).

В останній раз відразу п'ять гравців ПАОК грали в стартовому складі національної команди в товариському матчі Греція - Естонія 18.12.1999 (2-2). На поле тоді вийшли Стеліос Венетідіс, Γ.Χ. Геогіадіс, Пантеліс Константінідіс, Костас Фрадзескос і Нікос Фрусос.

Першим гравцем ПАОК, який надів капітанську пов'язку в національній збірній, став Ставрос Сарафіс. 27 липня 1969 команда, яка представляла нашу країну, грала товариський матч проти збірної Австралії в Мельбурні і «Цезар» вийшов на поле з пам'ятним вимпелом в руках. Збірна Греції перемогла тоді 2-0.

Ставрос Сарафіс чотири рази одягав капітанську пов'язку, в останній раз в матчі проти Польщі у Варшаві, в якому Греція поступилася 2-0. Капітанами національної збірної ставали також Йоргос Кудас, Кулис Іосіфідіс, Тодоріс Загоракіс, Костас Фрадзескос, Йоргос Георгіадіс, Костас Кацураніс і Дімітріс Салпінгідіс.