Основание ΠΑΟΚ прошло через множество стадий, которые начались в декабре 1925 и завершились 20 апреля 1926 официальным признанием команды судом первой инстанции Салоник. Процессы проходили в конце 1925 с участием руководителей административного и футбольного подразделений, членов Союза константинопольцев Салоник. Начальной целью было отделить спортивное подразделение от остального союза, созданного в качестве связующего звена между беженцами из Константинополя для работы с независимым руководством.

В пункте 27 начального Устава Союза константинопольцев Салоник говорилось: «Если в рамках общественного объединения будет создан и спортивный клуб, то он может стать независимым, имея и собственное название согласно регламенту Олимпийского комитета». Инициаторы данного процесса сначала просто добавили термин «Спортивный» к Союзу константинопольцев Салоник, но столкнулись с внутренними проблемами, так как руководство, которое они выбрали, было признано незаконным ввиду того, что решение о его формировании было принято Советом директоров, а не на Общем собрании акционеров.

«Борьба» обеих сторон длилась долго и Общее собрание от 7 марта 1926 вместо того, чтобы решить проблему, возникшую в декабре 1925, привело к полному расколу. После внутренних переговоров все, кто был против отделения организовали совместный фронт и взяли на себя руководство спортивным обществом. Набрав 92 голоса, президентом стал Никос Петропулос. Такое же количество голосов получил и его соратник Аристидис Мисиос.

Футболисты, инициировавшие разделение, не согласились с таким исходом и опубликовали в газетах следующий протест: «Заявляем о том, что мы подчинялись и подчиняемся первому и законному Совету директоров и действуем согласно его распоряжениям. Мы не желаем находится под вашим руководством, даже если он было законно оформлено». В ответ новый Совет директоров АЕК Салоники вычеркнул футболистов, пописавших заявление и направил их дело в союз футбольных ассоциаций Македонии и Фракии.

Другая сторона ответила на игровом поле и 28 марта 1926 в Салониках принимала на своем поле «Панатинаикос» в качестве «Спортивного общества константинопольцев». Поражение 5-0 было ожидаемым, ведь внутренние распри не оставляли времени на тренировки и правильный настрой на игру.

Следующий шаг был предпринят 30 марта 1926, когда в клубе константинопольцев собрались Триантафиллос Триандафиллидис, Константиниос Коемтзопулос, Константиниос Критикос, Михалис Теодосиадис, Иоаким Иоакимопулос, Аристодимос Димитриадис, Алехандрос Ангелопулос и Менелаос Цулкас, подписавшие протокол об учреждении нового спортивного клуба, чтобы процесс получил официальный характер.

5 апреля прошло Общее собрание, в котором приняли участие и футболисты команды. 20 апреля 1926 решением под номером 822 суд первой инстанции г. Салоники признал ΠΑΟΚ и несколько дней спустя команда провела свой первый товарищеский матч под своим окончательным названием.

Первой эмблемой ПАОК (1926) стало изображение четырехлистного клевера и подковы. Листья были зелеными, а над каждым из них стояла заглавная буква названия клуба. Эмблему придумал незабвенный Коемтзопулос, позаимствовавший идею у марки сигарет, которые он курил.

Первый Совет директоров ПАОК 1926-1927 сформировался в следующем составе:

Президент: Триантафиллос Триандафиллидис

Bице-президент: Панагиотис Калпакцоглу

Генеральный секретарь: Константиниос  Критикос

Специальный секретарь:  Менелаос Цулкас

Кассир: Иоаким Иоакимопулос

Футбольный директор: Алехандрос Ангелопулос

Спортсменов директор: Аристодимос Димитриадис

Советники: Панагиотис Малескас, Константинос Коемтзопулос и Михалис Теодосиадис.