| Tuesday 6th August 1996 | |||
| 1st Leg | |||
| Aarau | 4-0 | Lantana Tallinn | |
| Anorthosis Famagusta | 1-2 | Neuchatel Xamax | |
| Beitar Jerusalem | 1-5 | Bodo-Glimt | |
| BVSC Budapest | 3-1 | Barry Town | |
| Croatia Zagreb | 3-1 | Spartak Moscow | |
| Dinamo Minsk | 2-1 | Besiktas | (n) |
| Dinamo Moscow | 1-1 | Jazz Pori | |
| Dinamo Tbilisi | 2-1 | Molde | |
| Grazer AK | 2-0 | Vojvodina Novi Sad | (n) |
| Hajduk Split | 1-0 | Torpedo Moscow | |
| Halmstads | 0-0 | FK Vardar Skopje | |
| Helsingborgs | 1-1 | Dinamo 93 Minsk | |
| HJK Helsinki | 2-2 | Chernomorets Odessa | |
| IA Akranes | 0-2 | CSKA Moscow | |
| Iraklis Salonika | 0-1 | Apoel Nicosia | |
| Kosice | 0-0 | Celtic | |
| Legia Warsaw | 3-0 | FC Haka Valkeakoski | |
| Lyngby | 0-0 | Mura Murska Sobota | |
| Partizan Belgrade | 0-0 | National Bucharest | |
| Rapid Bucharest | 1-0 | Lokomotiv Sofia | |
| Sigma Olomouc | 1-0 | Hutnik Krakow | |
| Skonto Riga | 0-3 | Malmo | |
| Slavia Sofia | 1-1 | Wacker Innsbruck | |
| Sliema Wanderers | 0-2 | OB Odense | |
| Slovan Bratislava | 2-1 | Trabzonspor | |
| Zhalgiris Vilnius | 1-4 | Aberdeen | |
| Wednesday 21st August 1996 | |||
| 2nd Leg | |||
| Molde | 0-0 | Dinamo Tbilisi | (1-2) |
