Leeds tackle FC Zaporizhya from Ukraine, while Ipswich meet Yugoslav side Sartid Smederevo.
Fulham have arguably been handed the hardest tie of the three, with Jean Tigana's men being drawn against Croatians Hajduk Split.
Chelsea are up against Norwegian outfit Viking FK and Blackburn meet Bulgarians CSKA Sofia.
Scotland's Uefa Cup contingent saw Celtic being drawn against FK Suduva of Lithuania and Rangers facing Czech Republic side Victoria Zizkov.
The two Glasgow sides can expect to make it to the second round.
Aberdeen, however, must overcome German outfit Hertha Berlin who should provide a stern test.
And Livingston have also been handed a tricky tie against Austrians Sturm Graz, who have previous Champions League experience.
First round
Paris St Germain v Ujpest
Sporting Lisbon v Partizan Belgrade
Legia Warsaw v Utrecht
Real Betis v Zimbru Chisinau
Sarajevo v Besiktas
CSKA Moscow v Parma
Levski Sofia v Brondby
Anderlecht v Stabaek
National Bucharest v Heerenveen
Lazio v Xanthi
Aberdeen v Hertha Berlin
Ipswich v Sartid Smederevo
Maccabi Tel-Aviv v Boavista
AIK Stockholm v Fenerbahce
Sparta Prague v NK Siroki Brijeg
Austria Vienna v Shakhtar Donetsk Denizlispor v Lorient
Chelsea v Viking FK
Hapoel Tel-Aviv v Kaernten
VfB Stuttgart v Ventspils
Dinamo Zagreb v Zalaegerszeg
FC Copenhagen v Djurgarden
Victoria Zizkov v Rangers
Vitesse Arnhem v Rapid Bucharest
Leeds v Zaporizhzhya
Sevette v Amica Wronki
Sturm Graz v Livingston
Ferencvarosv Kocaelispor
Zeljeznicar v Malaga
Girondins Bordeaux v SKM Puchov
Slovan Liberec v Dinamo Tiblisi
Leixoes SC v PAOK Salonika
Litex Lovech v Panathinaikos
Red Star Belgrade v Chievo
Hajduk Split v Fulham
Primorje v Wisla Krakow
Graz AK v APOEL Nicosia
Celta Vigo v Odense
Donetsk v Werder Bremen
Celtic v FK Suduva
Porto v Polonia Warsaw
Gomel v Schalke 04
Grasshoppers v Zenit St Petersburg
Ankaragucu v Alaves
Anorthosis v Iraklis
FC Midtjylland v Varteks
CSKA Sofia v Blackburn
Slavia Prague v Excelsior Mouscron
First round matches to be played on 19 September and 3 October.