Az amerikaiak szerint az Afganisztánban menedéket talált Oszama bin Laden körüli iszlám mozgalom tervezi ezeket a merényleteket. Franciaország igen komolyan vette az amerikai figyelmeztetést, mert a német rendőrség december 25-én Frankfurtban felgöngyölített egy, a szélsőséges mozgalommal gyaníthatóan kapcsolatban álló kommandót, és ennek során fény derült egy Strasbourgban tervezett merényletre is.
A kommandó egyik tagját, a 34 éves algériai Mohamed Benszakriát június végén Dél-Spanyolországban tartóztatták le. A spanyol hatóságok szerint Oszama bin Laden európai helytartójának tartott férfi ellen július 12-én indult eljárás Párizsban, ahol be is börtönözték. A francia illetékes szolgálat, a DCRG (Direction Centrale des Renseignements Généraux) az amerikai figyelmeztetésről július 3-án jegyzékben értesítette az ország egész területén lévő valamennyi megyei szervezetét.
Később, július közepén az amerikaiak információkat kértek Franciaországtól egy francia-algériai állampolgárról. A 31 éves Zaharia Messzauit, aki a Saint-Jean-de-Luzben született Franciaország délnyugati részén, hamis útlevél birtokában tartóztattak le az Egyesült Államokban, amikor éppen pilótakiképzésben részesült tengerentúli járatokon közlekedő nagy hatótávolságú gépekre. A francia szolgálatok azonnal tudatták amerikai kollégáikkal, hogy Messzaui már a látókörükbe került, és gyanújuk szerint "afganisztáni zsoldos", akinek lakhelye London egyik külvárosában van, ahova az Afganisztánban tett utazásai között tért vissza. Messzaui, akkor megfigyelési, de nem letartóztatási céllal felkerült a keresett személyek listájára, ami azt jelenti, hogy jelezni kell mozgását, amennyiben fennakadna az ellenőrzésen. Korábbi híradások szerint a 31 éves férfit az Egyesült Államokban a kiadatási eljárásra tekintettel mostanáig őrizetben tartották. A férfi dossziéját a keddi merényletsorozat után kezdte alaposabban megvizsgálni az FBI és párizsi ügyészség is.