Новият клуб на Димитър Бербатов ПАОК е наследник на СК Хермес, който е основан през 1875 година от гръцкото общество в квартал Пера в Истанбул. Гърците в бившия Константинопол започнали да изграждат отбор, който бавно и постепенно набирал скорост.
 
Тимът печелил различни трофеи, но след гръцко-турската война 1921-22 година съществуването му в Турция станало почти невъзможно. Така се стигнало до 1926 година, когато гръцките ръководители и самите футболисти напуснали Истанбул и се преселили в Солун, където основали ПАОК. Абревиатурата се чете Пантесалоникиос Атлитикос Омилос Константинополитон, което в превод означава Всесолунски атлетичен клуб на константинополците.
 
Отборът играе домакинските си мачове на стадион „Тумба”. ПАОК е един от четирите клуба, който никога не са напускали местния футболен елит. Печелил е 2 пъти шампионската титла (1976, 1985), четири пъти купата (1972, 1974, 2001, 2003) и държи рекорда за най-много втори места - 12.