Чтобы урегулировать алжирскую проблему, он предложил новую конституцию, по которой Алжир объявлялся равноправным членом франко-африканского сообщества. Однако лидеры Фронта национального освобождения призвали бойкотировать референдум по конституции. Они считали, что речь может идти только о полной независимости Алжира. Все же референдум был проведен и получил одобрение 96,5 % населения. Несмотря на усилия правительства провести большие социальные и экономические преобразования в Алжире, вооруженная борьба продолжалась.
Начало правления нового правительства характеризуется решительными мерами и военными успехами. Разобравшись в ситуации, де Голль понимает, что время упущено и одним марш-броском нельзя решить алжирскую проблему. Уже с конца XIX столетия Франция переживала демографический упадок. Численность страны не менялась на протяжении 60 лет. Естественно, что удержать колонии со стремительным ростом населения было чрезвычайно сложно, а жители Франции в большинстве не были готовы сражаться за территориальную целостность страны. Президент справедливо говорил: «У арабов высокая рождаемость. Это значит, что если Алжир останется французским, то Франция становится арабской. Мне такая перспектива не нравится. Если мы не можем дать Алжиру равенство, то лучше предоставить ему свободу». Однако предоставление Алжиру свободы означало изгнание из страны миллиона живущих там уже много поколений французов. Поэтому во Франции развернулось героическое, но безрезультатное сопротивление под лозунгом: «Алжир – это Франция».
Осенью 1960 г. колонисты подняли восстание против официального Парижа, требуя продолжения борьбы за сохранение Алжира в составе Франции. Восстание потерпело поражение, но борьба за французский Алжир продолжалась.
29 января 1960 г. де Голль заявляет о праве Алжира на самоопределение, летом начинаются переговоры с Фронтом национального освобождения. Чуть позже в стране проводится референдум, на котором 75 % французов поддерживают предоставление Алжиру независимости. Военные не могут все это простить президенту. Генерал Массю объявляет, что ошибся в де Голле и не будет ему подчиняться. Естественно, генерала снимают со всех постов. Это было только началом неподчинения. Большая группа военных, политиков и интеллектуалов создает ОАС – вооруженную секретную организацию. В СССР ее почему-то называли фашистской. На самом деле это были люди, которые не привыкли отступать. Это были профессиональные военные, пользующиеся заслуженной славой. Например, подполковник Бастьен-Тьерри получил свой рыцарский крест из рук самого де Голля, но был казнен по его приказу за участие в заговоре. Восстание поддержали парашютисты Иностранного легиона. Путч возглавил генерал Рауль Салан. Однако армия метрополии не поддерживала мятеж. Никому не хотелось воевать.
28 апреля восставшие в Алжире были окружены танками, но генерал Салан успел скрыться. После провала быстрой атаки ОАС переходит к длительной осаде решений правительства. Организация мятежников приобретает четкую структуру. К осени 1961 г. в организацию входит более 4000 военных, сотрудников спецслужб и гражданских лиц, в основном из колонистов. Заговорщики организовали 15 покушений на президента, но судьба его хранила. От их рук погибли несколько тысяч сподвижников генерала и лидеров движения Сопротивления. Фактически в 1961–1962 гг. в стране велась малая гражданская война, где обе стороны проявляли жестокость и упорство. Действия ОАС привели к тому, что общественное мнение метрополии отвернулось от армии и колонистов. Их воспринимали как фанатиков, с которыми надо бороться. В результате большинство оазовцев были уничтожены или погибли при «странных» обстоятельствах, некоторые до сих пор проживают в Юго-Восточной Азии.
К этому времени относится пик алжирской войны. Арабские мятежники намеревались перенести войну в метрополию. В начале шестидесятых годов полиция Парижа нейтрализовала 60 арабских групп общей численностью почти в тысячу человек, занимающихся террористической деятельностью. Они планировали взрывы в метро и аэропортах, взрыв телецентра и даже массовые отравления через городской водопровод. Реально они организовали ряд терактов против полицейских.