Первой зацепкой стала емкость, которую преступники наполнили убойной начинкой. Обнаруженные осколки показали, что для размещения бомбы использовалась чугунная утятница с крышкой, которую прикрепили к корпусу стальными шпильками. Поиск завода-изготовителя занял два месяца, пока мастер Харьковского завода ленто-транспортного оборудования не узнал в остатках посудины свою продукцию. Именно такие утятницы были выпущены ограниченной партией и продавались в основном как подарочные на Украине, юге Советской России и в Закавказье. Среди конкретных городов фигурировали тот же Харьков, Ростов-на-Дону и Ереван.
Далее следователи выяснили, что скреплявшие корпус и крышку утятницы стальные шпильки произведены на Контакторном заводе в Ивановской области. В списке направлений, куда поступала продукция этого завода, оказалось 12 городов. Следователи провели аналогичное выяснение для других частей и материалов, из которых состояли взрывные устройства (болты, гайки, провода и т. п.) и сравнили повторяемость городов-потребителей. Чаще других снова повторялись Харьков, Ростов-на-Дону и Ереван.
Среди осколков были обнаружены металлические детали, которые преступники добавили в механизм для увеличения поражающей силы взрыва. Химический анализ осколков показал природную примесь мышьяка. Исходя из особенностей вещества, экспертам вскоре удалось установить рудник, где добывалась руда для этих деталей: Камыш-Бурунское месторождение в Крыму, недалеко от Керчи. Поставки металла с этого рудника ограничивались Украиной, Закавказьем и Литвой. Эти данные позволили сузить круг поиска до юга Украины, России и Закавказских республик, среди которых наиболее часто повторялась Армения.
Все эти сведения позволили отклонить первую версию случившегося, предполагавшую причастность мстительных москвичей, высланных «за сто первый километр» за совершенные проступки. Сложно представить, что теракты готовились в Подмосковье с применением материалов, закупленных в Закавказье, Украине или Литве.
Далее следователи предположили, что взрывы могли стать проявлением сепаратистских настроений, неизменно существовавших на окраинах Советского Союза. В некоторых украинских областях теплилось националистическое движение, в Литве действовали литовские экстремисты, в Армении пустили корни националистическая организация «Дашнакцутюн» и подпольная Национальная объединенная партия Армении. По версии следствия, преступные мотивы нужно было искать именно в растущем недовольстве союзных республик политической ситуацией в стране.
Несколько раз розыск преступников направлялся по ложному пути. Например, это случилось, когда в Тамбове в доме лесника Лобова при открытии почтовой посылки прогремел мощный взрыв, от которого погибла его семья. При обыске у главного подозреваемого, сторожа лесоводческого хозяйства Платова, был обнаружен часовой механизм, похожий на тот, который использовался в бомбах при взрывах в Москве. Вскоре местная милиция получила от него чистосердечное признание не только в убийстве семьи лесника, но и в совершении московских терактов. Прибывшие в Тамбов следователи КГБ допросили Платова по обстоятельствам взрывов. Подозреваемый сбивался, давал невнятные ответы, в целом показал полную неосведомленность в деталях происшествия. Стало очевидно, что тамбовская милиция «уговорила» Платова взять на себя вину за московские теракты. Покушение на лесника Лобова он действительно совершил по мотивам мести за издевательское отношение, но к взрывам в столице оказался непричастен.
Важной предпосылкой к раскрытию дела «Взрывников» стало установление места производства сумки, в которую была помещена бомба при взрыве в московском метро. По найденным на месте взрыва остаткам материала составили изображение предполагаемой сумки и распространили его среди сотрудников КГБ по всей стране. Помог случай. Дежуривший в аэропорту Ташкента сотрудник КГБ увидел у пассажирки похожую сумку. Выменяв ее на другую, он обнаружил на ярлыке место ее производства — Кожгалантерейная фабрика города Еревана. Следственные линии наконец скрестились в одной точке.
В то время как следственная группа вылетела в Армению, преступники поездом отправились в Москву для подготовки новых взрывов. Они снова объявились в столице к октябрю 1977 года. На этот раз масштабный теракт должен был совпасть с празднованием 60-летнего юбилея Октябрьской революции. Для обеспечения безопасности во время проведения праздничных торжеств Москву наводнили сотрудники правоохранительных органов. Повсюду можно было увидеть патрули, проверки документов, милицейские посты. Чувствуя пристальное внимание на каждом шагу, преступники побоялись распределить бомбы по нескольким объектам, поэтому решили взорвать их все в одном, но многолюдном месте — на Курском вокзале.