5月30日戴高乐用一整天时间来取悦社会民主党人。科隆贝的访客中，除了来向将军保证军队忠诚的朱安，其他人皆是政治活动家，有奥里奥尔·摩勒，默里斯·德肖内。将军热情而充满魅力，对他们礼遇有加。当然，将军已学会了讨人欢心的伎俩。摩勒回去告诉莫克：“这次会见是我生命中最重要的时刻之一。他是一个伟大，名副其实的伟人。”
翌日将军在科隆贝稍作停留，以此标志他“长期隐居”生活的约束，然后离开了那里。这一次，他的妻子陪着他踏上行程。是的，掌权已不过是个手续问题，将军确信他的新的篇章掀开了。
戴高乐一到巴黎，就在贝鲁斯旅馆会见了社会民主党的领袖们，并以一种最为谦和和最具说服力的姿态阐述了他的种种打算。除了弗朗索瓦斯·密特朗，其他社会民主党的领袖们勉强被说服了。议员团在表决中以77票对74票确认了戴高乐的领导。而这次表决极为重要，他决定着第二天的国民议会表决中戴高乐能否赢得多数。
表决那天，戴高乐本该在上午赶到国民议会，但遇到了一点阻碍。萨朗后来说，当时的气氛简直紧张到了极限，以至于吉沙打电话给他，让他准备实施复出行动。下午3点，戴高乐准备就绪。他赶到国民议会。他做简短发言时会场一片寂静，发言后他前往旅馆等待投票结果。消息传来，320票对224票，将军赢得了多数。尽管并非绝大多数而有些令人失望，但毕竟是多数。将军取得了胜利。复出行动最终被取消。
“我理解你们”
1958年6月2日上午，将军夫妇搬了家。他们离开佩鲁斯大厦的套房，住进马提农大厦，马提农大厦一直是法国总理们的寓所，但从家居生活考虑，这个地方并不合适。在这座规模可观的建筑中，居住区只包括四个房间。其中一间小沙龙，作为戴高乐夫人的客厅，但它紧挨着那间经常被派公用的餐厅。这座建筑比较正式的部分构成将军的“办公之所”，将军大部分时间都在他的办公室里度过。居所的条件实在不能让人满意。
但马提农是一个标志，将军把他的这次迁居视为必要的有象征意义的举动。全世界都该知道他再度掌权。而索尔法里诺街他手下中的大部分人也一起搬来，住在他的身边，包括他的内阁办公厅主任蓬皮杜和其他一些人。
当然新一届政府已宣布了它的组成人员名单。正如戴高乐后来所承认，这个政府的构成同他当初的打算不一样。他本希望能有一个北非人加入，最好是一个穆斯林。另外，还要有一个工会成员。但囿于当时的情况，就没有空位给这两个人。结果这一届政府又是成份混杂，许多新任部长在第四共和国时期就已广为人知，诸如摩勒、比内、普夫利姆朗。将军仿佛有意在强调政府的连续性。其他人都是文职人员，他们的工作便是唯将军是从。比如曾是维希政府的文职人员，当时为第四共和国驻西德大使顾夫·德姆维尔，便被人拖出波恩的高尔夫球场，担任外交部长。其他三个文职人员出任国防部长，内务部长和法国海外领地部长。终于有一些，而非全部，对将军忠贞不渝的人得以入阁，像德勃雷，马尔罗和爱德蒙·米什莱。但苏斯戴尔，帕莱夫斯基，卡特鲁，沙邦·戴尔马，富歇或者比约还不在此列。
阿尔及尔对如此的人事安排极其不满也难以接受。显而易见的功臣诸如萨朗，德尔贝克或者玛素，没有一个人得到任命。这绝非偶然，现在所发生的一切，正是1944年8月那一幕的重演。当时，至少在某种程度上，将军是在抵抗运动的支持下得以执政，便立刻将抵抗运动抛诸脑后。如今他又在重申他心中不可动摇的信条，即不论过去的抵抗运动或者现在的阿尔及尔，都不可以有任何超越法兰西之上的要求。政府代表法兰西，而他代表政府。
从国家的长远打算，将军最重要的任命，便是请他最忠诚干练的中尉米歇尔·德勃雷出任司法部长和新宪法筹备委员会主席。要在议会通过授权案绝非易事。将制定共和国宪法的权力交托某一政府在法兰西历史上还无这样的先例。过去都是由选举产生的立宪会议担当起这一责任。这是一个涉及基本原则的问题。
1958年6月3日，国民议会开会考虑为满足戴高乐接受总理任命的先决条件而提出的议案。处理阿尔及尔问题的特权很快得到批准，毕竟摩勒在1956年曾被授予同样的权力。政府在半年内有权发布法令这一条，尽管遇到较多阻力，但还是勉强被接受。然而宪法改革提案却引发无休无止的争执。