第四共和国名存实亡，戴高乐精心组阁。
戴高乐到阿尔及尔对暴乱群众说：“我理解你们。”
戴高乐修改宪法，稳住阿尔及利亚形势，最终当选法兰西第五共和国首任总统。
戴高乐于1958年6月1日当选总理，受命组阁后，便由一个乡村住户入主“马蒂尼翁大厦”。戴高乐夫人在大厦二楼的几个房间里静心地料理简朴而有规律的生活；这些房间里陈设着法国风格的家具。这曾是奥匈帝国大使馆的古建筑，现已改变了它阴暗的面貌。院子里不再是停车场，而每天有几个身着礼服的卫兵在那儿站岗。在漂亮的花园里养有不少家禽。在花园深处的音乐亭里设有一个哨兵。本来，将军因近几周来紧张操劳、多夜不眠，为准备复出经受了不少烦恼，应好好休息一下。但是，他必须立即着手改变为许多富有经验、知识、谋略的政治家所为之伤感的国家体制。而且，这时出现了戴高乐依靠议会授予的特权，彻底埋葬其深恶痛绝的第四共和国体制的大好时机。
6月3日，国民议会授权戴高乐制定新宪法并交由公民投票表决。同时，这天经共和国参议院同意，国民议会宣布永远休会。于是，第四共和国至此已名存实亡。
在组阁人选的安排上，充分显示出戴高乐已成为一位成熟的政治家。他安排居伊·摩勒和皮埃尔·弗林姆兰担任副总理，安托万·比内担任财政部长，无党派专家担任外交、国防和内政三个关键性部长。于是，内阁出现了这样的情况，好像第四共和国的一切变种“王公”都集聚到了发大水时的“诺亚方舟”上一样。参加内阁的戴派人物只有3人：司法部长米歇尔·德勃雷、前线战士事务部长埃德蒙·米什莱及情报部长安德烈·马尔罗。与此同时，同阿尔及利亚军事暴乱有牵连的苏斯戴尔等著名人物，一个也未应邀人阁。阿尔及利亚事务部长由戴高乐亲自兼任。这自然令极端殖民主义分子吃惊和不满。
戴高乐当然预见到了阿尔及利亚“极端分子”的反应，并立即给萨朗将军拍去了一封电报：“我将于星期三到您那里去。等着我，保持镇静，不要丧失信心。”
6月4日，戴高乐飞抵阿尔及尔，从机场到总督府，沿途受到群众欢迎。戴高乐在总督府大楼阳台上，面对集聚的人群，高举双手，直至最后欢呼声停息。那时，他说出了第一句话：“我理解你们。”接着，又是一片沸腾。下面，他继续讲话，讲话中大谈法国的兄弟情谊、伟大和豁达，但未谈到和他站在一起的叛乱领袖萨朗、苏斯戴尔等人所希望谈的问题，小心翼翼地避免了可能敏感的“法属阿尔及利亚”和“一体化”这两个词。
叛乱的头头们对戴高乐政府连苏斯戴尔都未吸收入阁甚为不满，但他们勉强掩饰这种情绪。可是，戴高乐早已察觉到一切，于是在同他们谈话时放风说，我的朋友苏斯戴尔很快会得到他应得到的高职任命。这时他们显得不安，因为没有让原陪伴阿尔及利亚事务部长戴高乐的社会党人勒博纳及其两个同事到阳台上同将军一起面对集聚的群众。原来，他们把这3个人突然捉起来，关进了邻近的房间。
戴高乐走遍阿尔及尔、君士坦丁、热纳、奥兰及莫斯塔加内姆等城。在一次集会上，当听到有人喊“苏斯戴尔万岁！”时，戴高乐发火了，对着麦克风叫道：“我请你们安静！安静！”叛乱的军队领导人慌张地看着将军，但沉默不语，等待事态的发展。他们都被戴高乐的威望和自信制服了。最后，在莫斯塔加内姆，他惟一的一次喊出：“法国的阿尔及利亚万岁！”他不是已经不同意“极端分子”了吗？为什么还要喊出这样的口号呢？在巴黎回答左翼伙伴的困惑时，他说，这句话是他“脱口”说出来的。他又说，平常说话时不也有人说：“法国的加拿大”，“法国的瑞典”？那只不过是口头上说说罢了。
戴高乐亲赴阿尔及利亚，解决了一个最迫切的任务：不同意“极端”纲领，但平息了叛乱。“极端分子”已经感觉到了这一点，于是6月5日德尔贝克通过阿尔及利亚电台发出警告说：“我们要团结在戴高乐周围，但要不惜任何代价……一定把5月13日开始的事业进行到底。”
不久，叛乱军人们应该因戴高乐亲手慷慨给他们授勋和晋升而感到满意了。萨朗获最高奖——军人勋章，马絮晋升少将，泽勒任军队参谋长，等等。7月7日，任命苏斯戴尔为情报部长之职。戴高乐想，这样可以更好地把这个不知疲倦的冒险分子置于自己的监督之下。7月14日国庆节那天，戴高乐向巴黎调来伞兵部队，并沿爱丽舍大街举行了阅兵式。巴黎亲眼目睹了戴高乐的强大威力：叛乱分子，原在5月份还使巴黎感到恐惧，而现在他们却成了最顺从的战士。
戴高乐就任总理后，在抓阿尔及利亚问题的同时，主要精力用于领导新宪法的起草工作。为了确保新宪法能符合他的意图，他把制定宪法草案的工作交由著名法律专家新任司法部长米歇尔·德勃雷负责。德勃雷领导一个由最高行政法院抽调的18名专家组成的小组，专门负责宪法草案的起草工作。而戴高乐则亲自领导一个包括政府办公厅主任乔治·蓬皮杜、戴派秘书处雷蒙·雅诺及老法律专家勒内·卡森在内的小组，主要负责为新宪法起草提供素材，即负责研究宪法内容并提交第一小组起草。
8月中旬，新宪法草案已经拟就。按照该草案，传统的法国议会程序已成为历史。为保证“三权分立”，明显地限制了议会的权力。根据该草案第16条规定，总统认为必要时可行使全权。不言而喻，谁都知道，这里所说的总统就是戴高乐。因此，新宪法草案充分体现了戴高乐在贝叶讲话的精神，为戴高乐登上政治舞台的顶峰奠定了基础。
新宪法草案完成后，戴高乐于8月20日立即出发，远访法属黑非洲。他当时在巴黎有很多事情要办，如果出访阿尔及利亚是可以理解的，因为那里曾发生叛乱，但为什么要迫不及待地出访相对平静的黑非洲呢？这是因为，他把批准新宪法和解决阿尔及利亚问题同非洲联系在一起了。战争时期，黑大陆是“自由法国”的基地，而如今黑大陆应是新法国“从敦刻尔克到塔曼拉塞特”的奠基石。新宪法规定建立大法兰西——非洲共同体。法国未来的总统希望也成为这一共同体的总统。
戴高乐在非洲各国受到热烈欢迎。回想起往日内心的创伤，他在西非首都说：“到达喀尔来，对我来说，总是满意的……在战争时期我这样是来不到达喀尔的！”戴高乐之所以受到热情接待，其原因很简单：非洲人愿把他视为解放者。而他也真的谈过，他们可能在全民投票公决新宪法时得到独立权。但是，戴高乐警告说，独立意味着立即同法国断绝一切联系。戴高乐力图使他们相信：只有大的联邦制复合体才有广阔前景。这一切都与阿尔及利亚问题有关。戴高乐在达喀尔说：“正是为了阿尔及利亚，我才建立这个共同体。”他指望阿尔及利亚人愿意参加这个共同体，从而使一切问题得以顺利解决。
的确，此时一切都很顺利。以雷诺为主席的立宪咨询委员会和最高行政法院先后通过新宪法草案并交由政府讨论。9月3日，政府批准了新宪法。9月4日，戴高乐在共和国广场讲话时宣布了新宪法草案，并呼吁全国人民在全民公决时投赞成票。他说：“如果你们否定了它，我们将立即重新回到你们所了解的歧途上去。如果你们赞成它，结果将使共和国更加强大而有效率。”
戴高乐9月4日在共和广场发表这一讲话，完全是由历史知识渊博的马尔罗精心策划的。因为1870年的这天，法兰西第二帝国崩溃，共和人士曾在这个广场欢庆胜利。发表讲话的目的是要让选民意识到，民主共和的原则必将会因戴高乐和第五共和国宪法而更放光彩。
为了加强对新宪法的宣传力度，新接任情报部长的苏斯戴尔开足宣传机器的马力，不断调整媒体人员，改进宣传手段，散发多种传单，号召法国本土、阿尔及利亚和其他海外领地的居民踊跃参加全民公决投票。
戴高乐1940年6月后第一次踏上法兰西大地（1944年）9月28日，是全民对新宪法投票公决的日子。在此之前，戴高乐说：“若能有70％的人投赞成票，那就是成功。”结果大大出乎戴高乐所料，在法国本土有80％的人，在海外领地有95％的人，都对新宪法投了赞成票。据说，在投赞成票的人当中，甚至包括了“法国的阿尔及利亚”的拥护者和戴高乐反对派的代表。不过，不少人投赞成票是出于对戴高乐的信任，而不意味着赞成新宪法。
那么，这部新宪法的内容是什么呢？戴高乐曾说：“关于这个决定一切的问题，我在12年前就已经公开阐明了它的主要内容，总的说来，我们要制定的宪法，应与人们称为‘贝叶宪法’的精神相符。1946年6月16日，我曾在贝叶提出了法国所必要的那种宪法。”实际上，这部新宪法完全体现了他“贝叶讲话”的原则：加强总统权力；稳定政府（内阁）地位；限制议会权力。
在加强总统权力方面，新宪法规定，总统拥有作为国家元首的主要权力，诸如颁布法律、缔结条约、主持国务会议及任命官员等等。宪法第11条规定，总统有权就某项政策措施直接提交人民表决。第12条规定，总统公布议会通过的法律，经征得总理和议长同意后，有权解散议会。第16条规定，总统有权在非常时期宣布全国处于“紧急状态”，行使“非常权力”，采取总统认为必要的一切措施。
在稳定政府（内阁）地位方面，新宪法对议会控制政府的不信任权加以种种限制。宪法规定，内阁总理可由总统直接任命，不需经议会同意。至于内阁成员，则由总理提名，总统任命。宪法还规定，议员不得兼任内阁成员，国会不信任案需议会1／10的议员签署并经过半数议员同意方可通过。
在限制议会权力方面，新宪法规定，实行以参议院为上院、国民议会为下院的两院制议会。议会的权力比第四共和国时期明显减少。其突出特点是：总统不由议会产生，拥有任命政府和解散议会的权力；议会的立法范围受到极大限制，条例性立法权限归属政府，议会通过的法案不一定成为法律。因此，有人把这种议会制称“半议会制”。
就是这样一部新宪法，确定了一直延续至今的法兰西第五共和国的政治体制。这一体制在稳定政局和增强对外行动能力方面，都是第三、第四共和国所无法比拟的。这部宪法的顺利通过也意味着大多数法国人接受了戴高乐治理国家的政治主张。
对戴高乐来说，这部新宪法的通过，是他政治生涯中最大的一次成功。他真感到如释重负，喜不自禁。现在，他可以专心致志地解决阿尔及利亚问题了。
1958年10月5日，法兰西第五共和国宪法正式公布。此后开始了戴高乐对阿尔及利亚政策的新阶段。10月23日，戴高乐在确立新体制后，举行第一次记者招待会。在招待会上，戴高乐要求阿尔及利亚起义者同意签订一项“勇士和约”，即在无任何政治保证的条件下干脆投降。自然，阿尔及利亚民族解放阵线和刚成立的阿尔及利亚临时政府不接受这个建议。与此同时，围绕着所谓“君士坦丁计划”即阿尔及利亚经济发展计划展开了一场吵吵闹闹的宣传。这时，戴高乐指望通过阿尔及利亚选举国民议会的办法，选出一些可能在解决阿尔及利亚问题上比民族解放阵线容易对付的穆斯林政治精英。但是这次选举是在“极端分子”监督下进行的，结果选出的代表绝大多数是拥护“一体化”的。这是不符合戴高乐原意的。因为一体化的拥护者实际上主张，对阿尔及利亚本地人只有一个对策——和解，即扩大无底的军事行动。
但是，此时还不能说一切无望了。不，仍有一定的办法。戴高乐渐渐削弱了“极端分子”，使他们脱离军界，把他们孤立起来。10月，他还下令一切军人退出“公共安全委员会”。为对此做出回应，10月16日“极端分子”宣布在阿尔及尔罢工，但是，罢工规模不大。鉴于此，戴高乐对在5月帮他取得政权的那些人员论功行赏。11月，他把萨朗将军从阿尔及利亚召回，赋予他一个纯荣誉性职务，让他接任国防总监。其他几个参加5月叛乱的将军也都被召回法国本土。
戴高乐极力使戴高乐分子脱离阿尔及利亚与法国“一体化”的最狂热的拥护者。10月1日，雅克·苏斯戴尔和其他原法兰西人民联盟的一些领导人在议会大选前组成了一个新的政党——保卫新共和联盟。戴高乐对过去的痛苦记忆犹新，坚决反对恢复法兰西人民联盟。这一次，他不仅不想同这个新党有任何正式联系，甚至反对他的弟弟皮埃尔·戴高乐参加这个戴派新党的领导委员会。他坚决反对苏斯戴尔企图把这个新党“保卫新共和联盟”同著名的“法属阿尔及利亚”的拥护者皮杜尔·莫里斯及杜舍联系在一起。戴高乐同苏斯戴尔在议会选举制度问题上发生冲突。他想使中间派政党和社会党人保持稳定的阵地，以抗衡苏斯戴尔及其他“一体化”捍卫者。
结果，在11月23日的议会大选中，上届议员仅有131人重新当选，议会中支持戴高乐的议员占了稳定的多数，戴高乐再也不必担心他的政策和措施会因议会障碍而不能实施了。
但是，戴高乐现在还不是总统。现任总统是科蒂，他的任期还有两年。戴高乐要登上总统宝座还需要一个过程，还需要经过竞选。
由于戴高乐对自己究竟能否得到全民支持并无十分把握，国家便决定采取间接选举法选举总统，即由参议员、国民议会议员、省市参议员、市长等各界知名人士组成的选举团选举总统。照此办法，12月21日举行了总统选举。结果，戴高乐获得近8万张选票中的78％，当选为法兰西第五共和国首任总统，是年戴高乐已68岁。