PAOK Thessalonikin koripallojaosto perustettiin pian emäseuran perustamisen jälkeen vuonna 1928. Vuonna 1959 joukkue voitti ensimmäisen Kreikan mestaruutensa. Kun Kreikan liigaa muutettiin ammattimaiseksi vuonna 1963, joutui PAOK sarjaporrasta alemmas A2 Ethnikiin. Seuraavaksi kaudeksi joukkue onnistui kuitenkin nousemaan uudestaan korkeimmalle tasolle. Putoaminen takaisin alemmalle sarjalle oli lähellä vuonna 1977, mutta PAOK onnistui voittamaan karsinnat.[1]
1980–luvulla seura kävi kovaa paikalliskamppailua Aris Thessalonikin kanssa kaupungin ykkösjoukkueen tittelistä. Kun joukkueet kohtasivat vuonna 1984 Kreikan cupin finaalissa, oli PAOK Thessalonikin silloinen valmentaja Faidonas Mathaiou käskenyt pelaajiaan ajamaan hiuksensa kokonaan pois. PAOK voitti finaalin luvuin 74–70 ja peli muistetaan nimellä “ajettujen päiden finaali”.[1]
1990–luvun PAOK aloitti vahvasti voittaen Saporta Cupin vuonna 1991. Seuraavanakin vuonna joukkue pääsi loppuotteluun, mutta joutui lopulta häviämään Real Madridille. Samana vuonna joukkue voitti Kreikan mestaruudenkin. Seuran viimeisin runkosarjan voitto on kaudelta 1992–1993, jolloin se voitti 26:sta pelistä 22. Samana kautena se pelasi ensimmäistä kertaa historiassaan Euroliigassa päästen aina Final Fouriin saakka. Toni Kukočin johtama Benetton Treviso vei kuitenkin voiton niukasti kahdella pisteellä. Korać Cupin voitto vuonna 1994 on seuran tähänastisen historian tärkeimpiä voittoja. Seuraavana kautena voitti Kreikan cupin ja vuonna 1999 tämä tapahtui uudestaan.[1]
