| Wednesday 17th July 1996 | |||
| 1st Leg | |||
| Anorthosis Famagusta | 4-0 | Shirak Gyumri | |
| B71 Sandur | 1-5 | Apoel Nicosia | |
| Becej | 0-0 | Mura Murska Sobota | |
| Beitar Jerusalem | 3-1 | Floriana | |
| Bohemians | 1-1 | Dinamo Minsk | |
| Croatia Zagreb | 4-0 | SK Tirana | |
| Dinamo 93 Minsk | 3-1 | Tiligul Tiraspol | |
| Dinamo Tbilisi | 4-0 | Grevenmacher | |
| FC Haka Valkeakoski | 2-2 | Flora Tallinn | |
| HIT Gorica | 0-1 | FK Vardar Skopje | |
| Hutnik Krakow | 9-0 | Khazri Baku | |
| IA Akranes | 2-0 | Sileks Kratovo | |
| Jazz Pori | 3-1 | GI Gotu | |
| Jeunesse Esch | 2-4 | Legia Warsaw | |
| KS Teuta Durres | 1-4 | Kosice | |
| Lantana Tallinn | 2-1 | IBV Vestmannaeyjar | |
| Maccabi Haifa | 0-1 | Partizan Belgrade | |
| Neftchi Baku | 2-1 | Lokomotiv Sofia | |
| Newtown | 1-4 | Skonto Riga | |
| Portadown | 0-1 | Vojvodina Novi Sad | |
| Pyunik Yerevan | 3-1 | HJK Helsinki | |
| Slavia Sofia | 4-3 | Inkaras-Grif' Kaunas | |
| Sliema Wanderers | 1-3 | Zestafoni | |
| Zhalgiris Vilnius | 2-0 | Crusaders | |
| Zimbru Chisinau | 0-4 | Hajduk Split | |
| Thursday 18th July 1996 | |||
| 1st Leg | |||
| Barry Town | 0-0 | Dinaburg | |
| St Patrick's Ath | 3-4 | Slovan Bratislava | |
| Tuesday 23rd July 1996 | |||
| 2nd Leg | |||
| Dinaburg | 1-2 | Barry Town | (1-2) |
| Grevenmacher | 2-2 | Dinamo Tbilisi | (2-6) |
