However, the Greek side could leapfrog Die Borussen in the table with victory over the Bundesliga giants.
PAOK will face Borussia Dortmund knowing that they need to rewrite history in order to beat the 2013 Champions League finalists.
The White-Blacks have not beaten a German team in European competition since 1981, when they beat Eintracht Frankfurt in the second leg of a Cup Winners' Cup tie.
Even then, PAOK still needed a penalty shootout to progress and they have failed to win any of these five most recent encounters with Bundesliga opposition.
However, the Thessaloniki outfit boast a promising record in this season competition, having won all three of their home games and scoring 12 goals.
While PAOK are led by former Juventus star Igor Tudor, there is a distinctly German flavour to their squad, with Dimitar Berbatov, Robert Mak and Ricardo Costa just three of seven first-team players to have plied their trade in the Bundesliga.
Furthermore, the Superleague outfit will hope to maintain their solid record in this competition. The Greek side have reached the group stages five times, progressing to the knockout phase on three occasions.
Recent form: WWDWDD
Recent form (all competitions): DLWDWW
Borussia had made a strong start to the season, but their form has tailed off in recent weeks with consecutive draws against Hoffenheim and SV Darmstadt, which has seen them lose ground on champions Bayern Munich.
However, prior to those draws, Dortmund had reeled off 11 consecutive victories in all competitions and Thomas Tuchel's side have found their goalscoring feet in Europe, having netted 19 in five outings.
Borussia's ability to keep hold of players like Marco Reus, Pierre-Emerick Aubameyang and Henrikh Mkhitaryan will have also helped Tuchel as he tries to build a team capable of challenging Bayern at home and to compete in Europe.
One key to Dortmund's early form has been a tight defence, with six goals conceded in seven league matches. However, they did concede five in their 11-5 aggregate win over Odd in the Europa League qualifying stages.
Goals have also been in rapid supply for the club, having netted 36 in their last 11 matches in all competitions.
Recent form: WWWWW
Recent form (all competitions): WWWWDD
Tuchel's main dilemma will be whether to rest players or go with a strong side for the early stages.
Reus missed the home victory over Krasnodar last time out due to a toe injury, but could feature in Thessaloniki.
Veteran keeper Roman Weidenfeller could also be in contention to replace fellow countryman Roman Burki in goal for Die Borussen.
Meanwhile, Berbatov might also make his first start in the group stages after being left on the bench for the goalless draw against Qabala.
PAOK possible starting lineup:
Olsen, Kitsu, Vitor, Costa, Tzavellas, Sabo, Tziolis, Pelekas, Mak, Athanasiadis, Berbatov
Borussia Dortmund possible starting lineup:
Weidenfeller; Ginter, Sokratis, Hummels, Schmelzer; Park, Gundogan, Reus, Mkhitaryan, Januzaj, Aubameyang
Head To Head
This will be the first time that the two sides have met.
We say: PAOK 1-2 Borussia Dortmund
Although Die Borussen's form has tailed off slightly over the past week, their form in Europe and their firepower would suggest that they can leave Greece with three points. PAOK's record against German clubs could also be a factor.