| Thursday 17th September 1998 | |||
| 1st Leg | |||
| Apollon Limassol | 2-1 | FK Jablonec 97 | |
| Arsenal Kiev | 0-2 | Lokomotiv Moscow | |
| Besiktas | 3-0 | Spartak Trnava | |
| Chelsea | 1-0 | Helsingborgs | |
| Heart of Midlothian | 0-1 | Mallorca | |
| Heerenveen | 3-1 | Amica Wronki | |
| Lazio | 1-1 | Lausanne-Sports | |
| Levski Sofia | 0-2 | FC Copenhagen | |
| Metalurgs Liepajas | 0-0 | Sporting Braga | |
| MSV Duisburg | 1-1 | Genk | |
| Newcastle United | 2-1 | Partizan Belgrade | |
| NK Rudar Velenje | 0-1 | Varteks Varazdin | |
| Panionios | 2-0 | FC Haka Valkeakoski | |
| Paris Saint-Germain | 1-1 | Maccabi Haifa | |
| Rapid Bucharest | 2-2 | Valerenga | |
| Ried | 2-0 | MTK Budapest | (n) |
| Thursday 1st October 1998 | |||
| 2nd Leg | |||
| Amica Wronki | 0-1 | Heerenveen | (1-4) |
| FC Copenhagen | 4-1 | Levski Sofia | (6-1) |
| FC Haka Valkeakoski | 1-3 | Panionios | (1-5) |
| FK Jablonec 97 | 2-1 | Apollon Limassol | (n) aet (3-3) |
| (Apollon Limassol won on penalties) | |||
| Genk | 5-0 | MSV Duisburg | (n) (6-1) |
| Helsingborgs | 0-0 | Chelsea | (0-1) |
| Lausanne-Sports | 2-2 | Lazio | (3-3) |
| (Lazio won on away goals) | |||
| Lokomotiv Moscow | 3-1 | Arsenal Kiev | (5-1) |
| Maccabi Haifa | 3-2 | Paris Saint-Germain | (4-3) |
| Mallorca | 1-1 | Heart of Midlothian | (2-1) |
| MTK Budapest | 0-1 | Ried | (0-3) |
| Partizan Belgrade | 1-0 | Newcastle United | (2-2) |
| (Partizan Belgrade won on away goals) | |||
| Spartak Trnava | 2-1 | Besiktas | (2-4) |
| Sporting Braga | 4-0 | Metalurgs Liepajas | (4-0) |
| Valerenga | 0-0 | Rapid Bucharest | (2-2) |
| (Valerenga won on away goals) | |||
| Varteks Varazdin | 1-0 | NK Rudar Velenje | (2-0) |









