Девять исламских террористических организаций немедленно взяли на себя ответственность за совершение этого преступления. На следующий день к ним присоединилась ранее неизвестная террористическая организация, именуемая себя «Пятый батальон Армии Освобождения». Но у следователей ФБР изначально не было ни одной зацепки, способной вывести на реальных виновников трагедии. Выдвигались самые невероятные версии. В какой-то момент власти США были склонны обвинить в совершении теракта боснийских сербов, которые могли совершить это нападение в отместку за поддержку боснийских мусульман. Однако эта версия была почти сразу отвергнута. Со времени взрыва прошло полтора дня. Расследование затягивалось. Террористов не удалось задержать по горячим следам.
Большие силы служб безопасности, включавшие сотрудников нью-йоркской полиции и агентов ФБР, сантиметр за сантиметром обследовали место взрыва, собирая по крупицам все, что могло иметь отношение к преступлению: фрагменты, которые могли оказаться частями взрывного устройства и автомобиля, элементами химических веществ, использованных для изготовления бомбы. Все это извлекалось из-под обломков и пыли и немедленно отправлялось на анализ. Криминалистические лаборатории изучили в этот день сотни разнообразных образцов, провели огромное число анализов, пытаясь установить тип взрывчатого вещества.
Решающий прорыв в расследовании наступил, когда агенты, работавшие в эпицентре взрыва, обнаружили 20-килограммовый кусок сильно искореженного металла. Он оказался фрагментом микроавтобуса и, к огромной удаче следователей, содержал номер корпуса. Получив в свои руки паспорт автомобиля, следователи легко проследили его судьбу и имя владельца. Микроавтобус «форд эконолайн» принадлежал агентству по прокату машин «Рейдер» и был арендован Мухаммедом Саламе, уже известным ФБР своими связями с исламистами.
4 марта 1993 года Мухаммед Саламе явился в агентство, чтобы забрать 400 долларов — залог за машину, которую он объявил угнанной накануне. Получив деньги, он собирался купить авиабилет и покинуть территорию США. За стойкой агентства находился сотрудник ФБР, еще более десятка агентов скрытно окружали здание. Мухаммеда Саламе задержали, когда он выходил из агентства.
Самого Рамзи Юсуфа захватить не удалось. Сразу после взрыва он под своим настоящим именем Абд эль-Басит Махмуд Абд аль-Карим беспрепятственно покинул США. Билет бизнес-класса в Пакистан был куплен заранее.
Спустя шесть дней, 10 марта 1993 года, был арестован еще один участник теракта — Нидаль Ияд, и почти сразу за этим задержаны остальные террористы: гражданин Ирака Абд аль-Рахман Ясин, Ахмад Аджадж и иорданец Ияд Исмаил — водитель заминированной машины. Агенты ФБР предложили Абд аль-Рахману Ясину сделку. За сотрудничество со следствием ему обещали существенно облегчить наказание. Ясин согласился, но, усыпив бдительность ФБР, ушел от агентурного наблюдения, скрылся в Иорданию, а оттуда перебрался домой в Ирак.
Еще один террорист, Махмуд Абу Халима, 1 марта 1993 года при помощи личного переводчика «слепого шейха» Сиддика Али, успел вылететь из Нью-Йорка в Саудовскую Аравию, а оттуда в Судан. Его имя вскоре всплыло на следствии, и Соединенные Штаты обратились к правительству Египта с просьбой о его задержании и экстрадиции. В Каире был дом родителей террориста, и можно было ожидать, что он у них объявится. Предположения оправдались. В первой половине марта Махмуд Абу Халима был арестован египетской службой безопасности. Американцы, однако, не торопили египтян с выдачей преступника. Методы дознания египетских служб безопасности существенно отличались от американских, запрещающих жестокое обращение с подследственным. Египтяне в таких случаях не церемонились, и когда специальный самолет доставил Махмуда Абу Халима назад в США, спецслужбы обеих стран уже располагали ценной информацией. Под пытками Абу Халима показал, что его группа занималась подготовкой покушения на президента Египта Хосни Мубарака во время его предстоящего посещения Нью-Йорка. На основании этих данных и несмотря на все заверения американской стороны о надлежащих мерах безопасности, Мубарак отменил свой визит в США.
Выяснилось, что террористическая ячейка Рамзи Юсуфа поддерживала теснейшие связи с египетскими террористическими организациями «Джихад аль-Ислами аль-Масри» и «аль-Джамаа аль-Исламийя». Тогда же впервые всплыло имя «слепого шейха». По словам Абу Халима, шейх Умар Абд аль-Рахман, вдохновитель убийства президента Египта Анвара Саддата, был главным идеологом исламистов, проживавших на территории Соединенных Штатов. Именно здесь вербовал свои Кадры Рамзи Юсуф.