Президентские выборы состоялись 21 декабря. Де Голль был избран на 7-летний срок. Так начиналась эпоха Пятой республики.

Генерал вступил в должность 8 января 1959 года. Премьер-министром он назначил Мишеля Дебре, поручив ему всю внутреннюю политику. Он сказал:

— Я не собираюсь вдаваться в детали правительственной деятельности. Я ограничусь лишь тем, что определю основные направления.

Основным приложением своих усилий президент считал внешнюю политику. Первым делом он поставил вопрос о равноправном положении Франции в структуре НАТО, где всеми делами заправляли США при полной поддержке Великобритании. 17 сентября 1958 года он направил Эйзенхауэру и Макмиллану меморандум, в котором указал: «Франция считает, что блок в его современной форме не может обеспечить условий безопасности всего свободного мира и, в частности, самой Франции. Ей представляется необходимым создание такой политической и стратегической организации, в которой бы она играла непосредственную роль»

Эйзенхауэр и Макмиллан отнеслись к предложению де Голля отрицательно, и не скрывали этого, хотя и не отказывались обсуждать эту тему на переговорах. Понимая, что англосаксы не собираются делиться полномочиями, президент Франции уже в начале 1959 года запретил базирование на территории своей страны американского ракетно-ядерного оружия и принял решение вывести французский Средиземноморский флот из-под командования НАТО.

Наступление на ФНО, обещанное де Голлем, началось в феврале 1959 года. Операцией руководил вновь назначенный командующий войсками в Алжире генерал Морис Шалль. Его план ведения боевых действий был назван «план Шалля». Он представлял собой серию операций, проходивших в различных районах до весны 1960 года. Их целью был разгром основных сил партизан и уничтожение их базовых лагерей.

В ходе типовой операции местные войска блокировали пути вероятного отступления партизан, пока высокомобильные подразделения парашютистов и Иностранного Легиона прочёсывали окружённый район. При этом широко использовалась высадка мобильных групп с вертолётов. По существу, французская армия в Алжире впервые в истории задействовала аэромобильные части.

Операции по «плану Шалля» имели сокрушительный эффект. Уже в марте 1959 года командование ФНО приказало своим силам максимально рассредоточиться и действовать группами не более отделения — взвода. В 1959 году ФНО потерял убитыми до 50% командного состава, были выведены из строя командующие всеми военными округами. По французской статистике, за период с конца 1958 по конец 1959 года Фронт потерял больше людей, чем за все предыдущие 4 года войны. По мнению канадского исследователя Эрика Улле, к 1960 году французская армия, по существу, одержала в Алжире убедительную военную победу, ставшую одним из немногих примеров успешной противопартизанской войны.

В начале апреля 1959 года президент де Голль по приглашению Советского правительства прибыл с официальным визитом в Москву (АИ, в реальной истории де Голль первым пригласил Хрущёва во Францию. Визит состоялся с 23 марта по 3 апреля 1960 г). Хрущёв решил «ковать железо, не отходя от кассы».

Хотя Никита Сергеевич и не мог уверенно произнести слово «экспромт», сама идея, что «экспромт удаётся лучше всего, если он хорошо подготовлен», ему понравилась. Он подготовил для президента Франции несколько сюрпризов, за которыми крылись предложения взаимовыгодного сотрудничества. Один из этих сюрпризов Хрущёв преподнёс президенту прямо в момент встречи.

Президент и Хрущёв выслушали гимны двух стран, вместе обошли строй почётного караула, обменялись речами, и в этот момент над аэропортом Внуково послышался низкий рокочущий рёв. Президент поднял голову... и замер с приоткрытым ртом. Над полосой заходил на посадку Ту-114 в раскраске «Аэрофлота» — (Посмотреть фото

Самолёт уже был оснащён усовершенствованными двигателями с многолопастными винтовентиляторами, поэтому шумел значительно меньше, чем в первых полётах 1957-58 гг. Это был первый образец, шасси на нём не меняли, сменили только двигатели. (АИ) Он коснулся полосы и покатился, плавно снижая скорость.

— Это наш новый дальнемагистральный лайнер Ту-114, конструкции товарища Туполева, — голос Хрущёва вывел президента из ступора. — Насколько я знаю, господин президент, заморские департаменты Франции широко разбросаны по всему миру. Сообщение с ними весьма затруднено. Не желаете ли осмотреть самолёт внутри? Думаю, он прекрасно смотрелся бы в цветах «Эр Франс»...

Хрущёв рассчитал точно. Де Голль согласился тут же, не раздумывая поломав дипломатический ритуал. Советская сторона предусмотрела его реакцию заранее, составив несколько вариантов расписания.

Ту-114 зарулил на стоянку, где уже стояли Ил-18 и Ту-110. Лимузин доставил президента и Первого секретаря к самолёту. Мадам Ивонн де Голль тоже пожелала полюбоваться самолётом, и Нине Петровне пришлось её сопровождать.

Президент самолётом не любовался, а подошёл к вопросу исключительно с деловой точки зрения.

— Какова его крейсерская скорость? — спросил де Голль.

Память на цифры у Хрущёва была прекрасная, и он запоминал не только количество кормовых единиц в кукурузе.

— 760 километров в час, — ответил Первый секретарь.

— С пропеллерами? — удивился президент. — А максимальная?

— Почти 850. (Реально было почти 900, но в АИ уширен фюзеляж)

— Не может быть!

Французская «Каравелла», с реактивными двигателями имела крейсерскую скорость 734 км/ч и максимальную 800 км/ч. Немудрено, что де Голль не поверил сразу. «Каравелла-3», следующая модификация, должна была взлететь лишь в декабре 1959 года, и её проектные данные были всё равно ниже, чем у советского самолёта, который уже летал.