Alan Shearer ga Newcastle ledelsen fra straffemerket etter 12 minutter. Da var grekerne blitt redusert til ti mann etter at Grigorios Georgatos la ned Newcastles Kieron Dyer.
33.000 hjemmefans på Karaiskaki-stadionet raste mot dommeren, men til ingen nytte.
Fire minutter senere sto det 1-1 etter en ny straffescoring, denne gang fra Predrag Djordjevic.
Laurent Robert sendte gjestene opp i 2-1-ledelse etter 34 minutter med et frispark.
Før pause skulle hjemmelaget få nok en utvisning, denne gang Athanasios Kostoulas. Han pådro seg sitt andre gule kort.
Patrick Kluiverts scoring etter 69 minutter gjorde at Newcastle vant 3-1 og sikret seg et meget bra utgangspunkt foran returmøtet på St. James' Park.
Seieren var den sjette for Newcastle og manager Graeme Souness.
For Olympiakos ble det en trist dag. Tapet var grekernes første på hjemmebane i europacupen denne sesongen, og tapet kom på klubbens 80-årsdag.