Переговоры продлились двое суток, но результатов не принесли; несколько вариантов освобождения заложников были забракованы генералом МВД Стариковым, и в итоге Карпухин принял решение готовиться к штурму вопреки возражениям Старикова. Обдумывая план спасения заложников, оперативники выяснили, что бандиты собирались сесть с заложниками в микроавтобус РАФ и на нём выехать к площади Ленина, где уже стоял вертолёт. Группа «А» решила заминировать микроавтобус, установив там маломощные взрывные устройства (обычную пиротехнику), которые оглушили бы бандитов и остановили бы автобус, но не причинили вреда заложникам. В распоряжении «альфовцев» было три группы: первая (старший — М. Я. Картофельников) штурмовала автобус, вторая (старший — Михаил Максимов) взрывала боковую дверь изолятора, а третья проникала через люк с четвёртого этажа на третий в здание изолятора. Однако в ходе операции произошло несколько накладок: изначально снайперским огнём планировалось уничтожить главарей бандитов, ради чего Прунчака хотели вызвать на переговоры, но он выставил вперёд своих подчинённых, которые передавали его ответы. В момент, когда должен был прогреметь взрыв, автобус не остановился, а проехал ещё от 15 до 20 м, прежде чем устройства сработали; стрельбу по салону вести нельзя было, поэтому оперативники стреляли по колёсам автобуса, хотя и бандиты отстреливались. В ходе операции оперативники должны были застрелить из бесшумного оружия сторожевую собаку, которая могла своим лаем лишить группу фактора внезапности, но кто-то из солдат, не желая убивать животное, увёл собаку в безопасное место, сохранив ей жизнь и не позволив выдать группу звуками. Также был риск того, что при взрыве боковой двери изолятора может рухнуть всё здание, которое де-факто находилось в аварийном состоянии.
Тем не менее, усилиями «Альфы» удалось и освободить всех заложников, и обезвредить преступников в автобусе и в самом изоляторе. В ходе операции лёгкое ранение получили сотрудник «Альфы» И. В. Орехов (ранен в шею бандитом из пистолета Марголина) и один из бойцов «Витязя» Олег Лебедь, который рвался к люку на крыше изолятора (ранен в ногу, чтобы не подползти к люку и не нарваться на огонь бандитов). Операция стала редким отечественным и мировым примером, когда подразделения спецназа использовались для освобождения заложников, захваченных в пенитенциарных учреждениях. Через несколько месяцев в СССР с визитом прибыл бывший президент США Ричард Никсон, которому обеспечивали охрану двое бойцов «Альфы»: от одного из них, коим был Максимов, Никсон и узнал историю о бунте в Сухуми, однако не поверил в её подлинность, сказав, что при таком огромном количестве стволов в своём распоряжении заключённые должны были отбивать штурм без проблем. Полковник Карпухин же за удачное проведение операции по освобождению заложников был произведён в генерал-майоры.