По факту совершенного преступления было возбуждено уголовное дело по статье 277 Уголовного кодекса РФ — посягательство на жизнь государственного или общественного деятеля, — которое находилось в производстве следственной службы петербургского УФСБ. По данным на 18 мая 2002 года, по этому делу допрошено более тысячи свидетелей, проведено 40 обысков, 26 выемок документов, 62 осмотра и 104 экспертизы, в том числе «уникальных с научной точки зрения». В ходе расследования была арестована группа киллеров, причастных к совершению других преступлений. В течение двух лет по делу было опрошено около 800 свидетелей, проведено огромное количество экспертиз.
Следствие разрабатывало три основные версии преступления — политическую, экономическую и бытовую. Однако Руслан Линьков и сподвижники по партии настаивали именно на политической версии гибели депутата. А вот бывший тогда директором ФСБ РФ В. В. Путин заявил: «У меня нет никаких оснований полагать, что это политическое убийство — пока». При этом он заверил, что «и ФСБ, и другие правоохранительные органы, и государство в целом сделают все возможное для расследования этого преступления».
Но время шло, а результатов не было. Адвокат потерпевшей стороны Юрий Шмидт жаловался, что представители ФСБ отказывают родным депутата в предоставлении материалов о ходе расследования преступления, ссылаясь на то, что следствие еще не закончено. В свою очередь в УФСБ заявляли, что «действия следственной группы не противоречат закону и направлены на предотвращение возможных утечек информации, касающихся этого дела» и само дело «находится на особом контроле, и темпы по его расследованию не снижаются».
Бывший помощник Старовойтовой Линьков неоднократно говорил, что «следствию стоило хотя бы в качестве свидетеля допросить, в первую очередь, Геннадия Николаевича Селезнева». На вопрос, не означает ли это, что он считает Селезнева причастным к смерти депутата, ее бывший помощник ответил: «Между Старовойтовой и спикером Госдумы было много конфликтов. В свое время Старовойтова занималась расследованием ряда дел, в том числе деятельностью Академии национальной безопасности, к которой имеет отношение Селезнев». И добавил, что академия «занималась аккумулированием средств, которые должны были использоваться в дальнейшем в качестве предвыборного фонда спикера Думы». Однако следствие не подтвердило возможной причастности к убийству Галины Старовойтовой спикера российского парламента Геннадия Селезнева, о чем ранее заявлял сопредседатель санкт-петербургского отделения партии «Демократическая Россия» Виктор Кривулин.
И все же виновники убийства Старовойтовой были найдены и взяты под стражу в ноябре 2002 года. Материалы дела в отношении шестерых обвиняемых были переданы в горпрокуратуру 24 ноября 2003 года и через несколько дней поступили в суд. Всего, по версии следствия, к убийству Старовойтовой причастны 11 человек. Однако на скамью подсудимых сели только шестеро, а в розыске остались еще пятеро подозреваемых. Всем арестованным предъявлены обвинения. В числе задержанных по «делу Старовойтовой» были уроженцы города Дятьково Брянской области: близкий к так называемому тамбовскому преступному сообществу тридцатичетырехлетний Юрий Колчин, бывший сотрудник Главного разведуправления Генштаба, затем работавший личным шофером одного из лидеров тамбовской преступной группировки в Петербурге (до этого дважды судимый за сопротивление сотрудникам милиции и незаконное хранение оружия), двадцатитрехлетний Игорь Лелявин, а также Алексей Воронин, Юрий Ионов, Виталий Акишин, Игорь Краснов. Петербуржцы Сергей Мусин и Павел Стехновский, Евгений Богданов и Олег Федосов находились в розыске. Их дело расследовалось параллельно и было выделено в отдельное производство. Заказчика убийства депутата так и не установили. В этой части дело также выделено в отдельное производство, и расследование продолжается по сей день.