В середине 1950-х годов голлистское движение почти полностью потеряло свое влияние в стране. Де Голль отдалился от политики и почти безвыездно жил в Коломбэ. Его самые верные сторонники, объединившиеся в небольшую партию «социальных республиканцев», на парламентских выборах 1956 года получили всего 21 место в Национальном собрании. Тем не менее они не теряли надежды когда-нибудь вернуться к власти. В Париже известные голлисты Мишель Дебре, Жак Сустель, Жорж Помпиду, Эдмон Мишле каждую неделю собирались в Доме Латинской Америки. Иногда на эти встречи приезжал и Андре Мальро. Голлисты не забывали и о своем лидере. Время от времени они приезжали к де Голлю в Коломбэ. Мальро, конечно, тоже.
Между тем Четвертая республика, ослабленная колониальными войнами и нестабильностью собственной политической системы, вступила в полосу затяжного кризиса. Роковой для нее оказалась алжирская война. В Алжире все время нарастало недовольство со стороны офицеров сражающейся там французской армии и местных ультраколониалистов непоследовательностью алжирской политики парижских кабинетов. Голлисты решили воспользоваться этой ситуацией. Они тайно налаживали контакты c недовольными и пытались склонить их выступить с призывом к де Голлю. Сторонникам генерала удалось это сделать во время алжирского антиправительственного мятежа, поднятого «ультра» 13 мая 1958 года и поддержанного армией. Де Голль умело воспользовался действиями мятежников и смог вернуться к власти на продиктованных им условиях. 1 июня Национальное собрание утвердило его в качестве председателя правительства.
Мальро не знал о деятельности голлистов в Алжире. События застали писателя в Италии. Он прибыл в Париж и попал «с корабля на бал». Де Голль тут же предложил ему портфель министра. В течение второй половины 1958 года во Франции был установлен новый политический режим – Пятая республика. Мечта де Голля о сильной исполнительной власти, ставшая основной идеей голлизма, воплотилась в жизнь. Республика парламентского типа правления заменялась президентской республикой, что было закреплено Конституцией 1958 года.
В конце года де Голль был избран первым президентом Пятой республики. Он оставался на своем посту более десяти лет. Андре Мальро все это время занимал пост министра культуры в высоком ранге государственного министра. Президент предоставил ему полную свободу действий. Он понимал, что такая ярчайшая личность, как Мальро, сделает культурную политику Франции по-настоящему значимой и неповторимой.
Новый министр был очень рад своему назначению. Он сразу начал размышлять над тем, чем же предстоит заняться его министерству. Однако в конце 1950-х – начале 1960-х годов писателю пришлось много времени уделять пропаганде установленного де Голлем режима. Несравненный opaтор, Мальро с удовольствием стал глашатаем «новой Франции»: он объехал многие страны, чтобы возвестить о возвращении к власти великого француза и установлении им режима, достойного его великой отчизны.
В конце 1958 года Мальро побывал во французских колониях Гвиане и Мартинике в Америке, съездил в любимые им страны древних азиатских цивилизаций – Иран, Индию и Японию. В Индии он встречался и беседовал с Неру. В 1959-м министр отправляется в большое турне по Латинской Америке, останавливаясь в столицах Аргентины, Чили, Бразилии, Боливии, Колумбии, Эквадора, Парагвая, Уругвая и Венесуэлы. Он возвращается в Париж в конце года‚ a в начале следующего года опять летит в Америку, нa этот раз – в Мексику.
Мальро стал блестящим проводником выдвинутой де Голлем идеи деколонизации. В 1960 году министра с энтузиазмом принимают в только что получивших независимость бывших французских колониях – Чаде, Габоне и Центральноафриканской Республике. Очень тяжелым был путь к самостоятельности лишь одной французской колонии – Алжира. Вообще «алжирская проблема» оставалась главной для всей французской политики в первые годы существования Пятой республики. Европейское население этой страны, в большинстве своем ультраколониалистское, отчаянно боролось за сохранение колонии под французским суверенитетом. Его по-прежнему поддерживала армия. Колониальная война не прекращалась. В 1960 и в 1961 годах сначала «ультра», a затем генералы армии подняли в алжирской столице мятежи против политики де Голля, направленной на предоставление Алжиру независимости. Мало того, на территории Франции начала подпольно действовать так называемая Вооруженная секретная организация (ОАС), объединившая сторонников «французского Алжира» и действующая террористическими методами.