ВГС возглавил M. Будиаф, один из исторических лидеров алжирской национально-освободительной борьбы. Он терпимо относился к деятельности политических партий и к критике в адрес ВГС, но по отношению к ИФС занял жесткую позицию, и ИФС принял решение о вооруженном восстании. 29 июня 1992 г. М. Будиаф стал жертвой покушения. Новым председателем ВГС был избран полковник А. Кафи. В июле 1993 г. председателем ВГС и министром обороны стал генерал Л. Зеруаль. К этому времени число жертв исламистов продолжало возрастать.
20–25 января 1994 г. Конференция национального согласия определила политическое развитие страны после роспуска ВГС. В ней участвовало большинство политических партий, кроме ИФС, ОКД, ФНО и ФСС, а также две умеренные исламистские партии – ХАМАС («Харакат муджтамаа исламия», или Движение исламского общества) и «Ан-Нахда». На конференции была принята Платформа политических действий: власть в течение переходного периода должна была принадлежать временному президенту, правительству и Национальному переходному совету. 1 февраля 1994 г. ВГС самораспустился, президентом был назначен Л. Зеруаль. Именно при нем в 1994–1995 гг. происходили наиболее ожесточенные и крупномасштабные столкновения между исламистами (Вооруженным исламским движением, находившимся под влиянием ИФС и которое с июня 1994 г. стало называться Исламской армией спасения (ИАС), признавшей себя вооруженным крылом ИФС; Вооруженные исламские группы) и армией. В боях с исламистами участвовали и отряды самообороны алжирцев, противников исламизации государства и общества, их ряды пополняли родственники убитых исламистами. Во второй половине 1993 г. часть военной верхушки проявила готовность к началу переговоров с умеренными элементами ИФС. В самой армии произошел раскол на умеренных и радикалов. Сам ИФС отказался от переговоров, настаивая на предварительном освобождении десятков исламистов. Диалог так и не начался.
В своей первой речи как главы государства Л.Зеруаль призвал к серьезному диалогу, чтобы разрешить кризис в стране, и подчеркнул роль армии в обеспечении национального согласия. В марте 1994 г. распространились слухи о разногласиях в вооруженных силах в связи с новыми попытками вступить в переговоры с исламистской оппозицией. Генерал М. Ламари, начальник генерального штаба, выступавший против диалога с исламистами, все же счел необходимым подтвердить доверие армии к Л. Зеруалю. В мае 1994 г. в рамках содействия диалогу с исламистами и другими оппозиционными организациями Л. Зеруаль сформировал группу из 6 известных общественно-политических деятелей. Однако контакты с двумя освобожденными лидерами ИФС Джадди и Бухамханом ничего не дали. В августе 1994 г. ФНО, Партия алжирского обновления, Движение за демократию в Алжире (партия Бен Беллы) и умеренные исламистские организации приняли участие в диалоге с правительством. На следующей встрече в сентябре в рамках национального диалога обсуждались письма А. Мадани, в которых он соглашался уважать конституцию 1989 г., принцип сменяемости власти и упомянул о возможности примирения. В середине сентября Л. Зеруаль объявил об освобождении А. Мадани и А. Бенхаджа из тюрьмы и переводе их под домашний арест. В знак протеста против контактов с исламистами в сентябре 1994 г. в Кабилии была проведена всеобщая забастовка. С учетом ситуации в Кабилии и условий, выдвинутых исламистами (отмена постановления о запрещении ИФС, освобождение всех лидеров ИФС и участие ИАС в переговорах), Л. Зеруаль был вынужден прекратить диалог с ИФС. В октябре он заявил, что ни М. Мадани, ни А. Бенхадж не желают отказаться от насилия или участвовать в переговорах. Л. Зеруаль принял решение о проведении президентских выборов до истечения своих полномочий.
В ноябре 1995 г. Л. Зеруаль был избран президентом Алжира. Согласно официальным данным, несмотря на призывы ИФС, ФНО и ФСС бойкотировать выборы и угрозы исламистов, 75,7% избирателей явились на выборы. Л. Зеруаль получил 61% голосов. Лидер ХАМАС М. Нахнах, занявший проправительственную позицию после военного переворота 1992 г., заручился поддержкой 25,6% избирателей, генеральный секретарь ОКД С. Саади – 9,6%. Это были первые альтернативные президентские выборы в Алжире. Кандидаты оппозиционных партий, в том числе лидер исламистской партии М. Нахнах, могли свободно проводить политические собрания и критиковать правительство. Обращало на себя внимание участие в выборах большого числа женщин, несмотря на угрозы исламистов. Большинство их не носило хиджаб, девушки были в мини-юбках. Один алжирец сказал по поводу этих выборов: «Я знаю людей, которые голосовали тогда за ИФС, но ни в коем случае не проголосовали бы за него теперь. Голосование в 1991 г. носило протестный характер, и теперь алжирцы увидели истинное лицо ИФС». Президентские выборы показали, что алжирцы устали от длительного вооруженного столкновения и многие разочаровались в ИФС, они возлагали надежду на стабилизацию Л. Зеруалем ситуации в стране, тем более что тот в своей предвыборной кампании обещал гарантировать мир и безопасность. Определенную роль в избрании Л. Зеруаля сыграла его предыдущая деятельность.
Он не был связан с использованием военной силы для подавления выступления масс в октябре 1988 г., не принимал участия в отмене парламентских выборов в январе 1992 г. Будучи министром обороны, еще до своего назначения президентом вел переговоры с находившимися в тюрьме исламистскими лидерами, пытаясь прекратить насилие в стране. Он совершенствовал свое военное образование в основном в Советском Союзе и в Иордании, а не во Франции. Демонстрируя готовность к национальному согласию, поддерживая умеренное течение в исламистском движении, президент включил двух представителей ХАМАС в состав правительства, сформированного в январе 1996 г.
В апреле 1996 г. президент начал трехнедельные переговоры с оппозиционными партиями, профсоюзами и общественными организациями, в том числе с умеренными исламистскими организациями ХАМАС и «Ан-Нахда», в рамках подготовки к парламентским выборам. В июне 1996 г. Л. Зеруаль предложил внести изменения в конституцию 1989 г. 28 ноября 1996 г. состоялся референдум по новому тексту конституции. Согласно официальным данным, в нем приняли участие 79,8% электората, из них 85,8% поддержали внесение поправок. Некоторые оппозиционные партии обвинили правительство в подтасовке результатов голосования. В ходе референдума были допущены многочисленные нарушения и фальсификация. Власти не допускали наблюдателей в избирательные участки. Проберберские ОКД и ФСС призвали избирателей бойкотировать референдум или голосовать против проекта конституции: в Кабилии крайне негативно отнеслись к этому проекту, поскольку арабский язык фактически провозглашался единственным национальным языком Алжира. Конституция значительно расширила права президента, усилила контроль исполнительной власти над законодательной. В 42-й статье 4-й главы подчеркивалось, что политические партии не могут создаваться на лингвистической, расовой, корпоративной или религиозной основе и что политические партии не могут прибегать к пропаганде, затрагивая упомянутые элементы. Однако несмотря на эту статью, правительство продолжало терпимо относиться к деятельности умеренных исламистских партий. Чтобы соблюсти формальность, исламисты из ХАМАС переименовали свою партию в Движение общества за мир, чтобы участвовать в парламентских выборах.
К концу 1996 г. вооруженные группы исламистов стали избегать столкновений с армией. Они понесли большие потери в результате эффективных действий правительственных сил, отрядов самообороны противников исламистов, нарушилась координация их активности, и усилились разногласия в их рядах. С начала 1995 г. шла вооруженная борьба между Исламской армией спасения и Вооруженными исламскими группами, приводившая к ослаблению радикального исламизма. Произошло улучшение обстановки в ряде регионов. Вначале США, учитывая возможность прихода исламистов к власти, поддерживали с ними контакты и вели переговоры на «низком уровне». В 1995 г. Вашингтон под влиянием аналитического доклада, где делался вывод о невозможности военной победы исламистов, ужесточил свою позицию в отношении ИФС. После избрания Л.Зеруаля президентом в ноябре 1995 г. Вашингтон активизировал экономические и военные отношения с Алжиром. Прямые американские капиталовложения США в алжирскую экономику возросли со 135 млн. долларов в 1994 г. до 600 млн. в 1996 г.
На встрече в Мадриде в апреле 1997 г. основные оппозиционные партии, в том числе ИФС, призвали правительство к переговорам ради достижения мира. Они подчеркнули, что лишь политическое решение покончит с насилием. Правящий режим отказался пойти на какие-либо уступки и отверг предложение ИФС начать диалог.