与此同时，他小心地做了非殖民化的第一步尝试：和摩洛哥、突尼斯两国首脑签订了从两国领土上撤军的协议，仅保留了五个战略军事要塞。6月9日，他委任萨朗将军为总司令和阿尔及利亚的总代表；过了几天，又分别任命阿拉尔将军和马絮将军为阿尔及尔最高行政长官和行政长官。
人心粗定之后，戴高乐按照循序渐进的战略思想，不时地有计划地暗示阿尔及利亚人民将有“选择的余地”。
但要真正解决这些问题，惟一能保证戴高乐采取行动的工具就是新共和国的宪法。他清楚地认识到，第四共和国的宪法包孕着毁灭她自身的因素；所以一出台他就激烈地反对她。他所谋求的，是一个强有力的根本大法。为了尽快实现将军的这一夙愿，司法部长米歇尔·德勃雷和他的由18名法律专家学者组成的立宪委员会日以继夜地工作，在贝叶讲话的骨架上增肌添肉。同时，戴高乐亲自组织了四名部长充当立宪顾问，并设立了一个39人的立宪咨询委员会协助工作。
8月14日，新宪法草案定稿。这个草案规定：第五共和国的总统将通过由议会议员、各省议员及其他知名人士组成的选举团以间接投票选举产生，任期七年。总统有权挑选自己的总理和解散议会。如果政府（如果国会正在开会）或者两院共同提出什么特别问题，总统还有权就这些问题组织全民表决。尤其是在严重的危机时刻，根据宪法第16条，总统可以行使全权。简言之，这是一部准总统式的宪法。比起法国过去的宪法来，在借鉴美国宪法方面算是最多。
此外，关于法国与海外附属国的关系，宪法草案保留了一个可供进一步选择的因素。戴高乐亲自规定：每一个领地都可以自行决定，或是保持现状，作为部分自治的国家加入共同体，或是与法国合并，作为一个海外省份，甚或完全退出法国共同体。如果他们想得到法国的援助和保护，那么他们最多只能地方自治；如果他们还打算自定外交政策，那就必须与法国中断包括感情在内的一切关系。
为了使草案尽快成为自己行使权力的工具，将军真是尽了最大的努力。8月20～29日，将军访问了马达加斯加、乍得、中刚果（布拉柴维尔）、乌班吉沙里（现中非共和国）、象牙海岸、几内亚、塞内加尔、上沃尔特、达荷美、加蓬、尼日尔和毛里塔尼亚，到处解释、呼吁人们投票支持他的宪法。在国内，苏斯戴尔则开动了强大无比的宣传机器：用飞机放烟形成空中广告，放宣传电影电视片，到处贴标语、免费发行上千万份《法国全民表决》刊物，敦促人民去投票。
9月3日，政府通过了宪法草案；4日，戴高乐在共和国广场公开讲演，公布全文并呼吁人民批准。28日，这部草案终于以本土80%、海外95%的赞成票获得通过，并于10月5日正式公布。戴高乐在他的政治生涯中，终于赢得了最辉煌的一次胜利——为开创第五共和国奠定了坚实的基础。
接下来的事便顺理成章了。1958年12月21日，法兰西“各界知名人士”把他们的8万张选票的78%按时给了戴高乐，正式向全世界宣告法兰西第四共和国从此灭亡，第五共和国诞生！1959年1月8日，新总统正式拜访前总统。前总统用这样的祝词欢迎他：“法国人中的第一位人物现在终于成为法国的第一人了。”在人们“谢谢科蒂”和“戴高乐万岁”的欢呼声中，他们并肩乘坐总统专车前往凯旋门，按传统去向“无名战士”致敬。
现在，戴高乐终于可以专心致志地拔掉阿尔及利亚这个定时炸弹上的雷管了。穆斯林领导人已于1958年9月19日宣布把民族解放阵线组织改为阿尔及利亚共和国临时政府，他们的政治态度一如戴高乐，也是不低头，不妥协。戴高乐却希望通过调停谈判，和平解决。为此，他做了许多微妙的准备工作，首先是尽可能多地调走那些坚持“法国的阿尔及利亚”思想的军官，或解除他们的军权。他任命最具潜在危险的萨朗将军为国防部最高检察长，提升他的副手莫里斯·夏尔将军继任总司令。接着调动或强令退休1500多名中高级军官。
为了缓和穆斯林分子的不妥协态度，在爱丽舍宫1月8日举行的新总统就职典礼仪式上，他讲了几句预示性的话：“一个和平和革新的、按照自身的方式发展其个性、并同法国密切联系的阿尔及利亚，将有其选择的地位。”五天后，他主持了一次内阁会议，宣布了一些范围广泛的宽大措施：大约7000名嫌疑分子可从阿尔及利亚的俘虏营中获释，180名被判死刑的人将缓期执行。同时被关在巴黎桑泰监狱的民族解放阵线领导人本·贝拉的对手、阿尔及利亚民族运动党的年迈领导人迈萨利·哈杰，则被从贝尔岛的拘留所里释放，并随即被送到巴黎郊外的寓所里。
在随后的会议、各省视察和讲演中，将军不断地暗示他的阿尔及利亚政策，把海内外法国人的注意力和思维方式慢慢往“阿尔及利亚是阿尔及利亚人的阿尔及利亚”方向引导。他告诉军队：与阿尔及利亚民族解放军作战是“一次毫无结果的斗争”，仅仅赢得战争是不够的，欧洲人直接统治的时代已经一去不复返了，没有阿尔及利亚人的同意，在那里什么也办不成。他严厉地警告军队：“你们不是为军队自身谋利益的军队，你们是法国的军队。你们的存在仅仅是为了法国，并为法国效力。就我的职位和责任来说，我必须要求军队的服从。只有这样，法兰西才能生存下去。我相信你们会这样做的，我代表法国感谢你们。”
9月16日，戴高乐发表电视讲话，首次公开冒风险提出“在恢复和平后四年内让阿尔及利亚人自决”问题，并把这种“自决”解释为三种选择：分离、一体化、内部自治。他明白无误地说：在阿尔及利亚人能够决定他们的命运之前，撤回在阿尔及利亚的法国军队，这点必须包括在条件以内。
在11月10日的记者招待会上，戴高乐又重申他关于自决权的建议，并提出确保愿到法国会谈的民族解放阵线任何代表的安全。他的政策，使五个在阿尔及利亚的欧洲人极端分子组织惊惶不安。他们举行示威游行，反对总统的政策。民族解放阵线也趁机制造事端，制造残杀欧洲人的恐怖活动，使局势益加混乱。驻军伞兵司令马絮将军轻率地对新闻界说“我们再也无法理解戴高乐的政策了”，并说军队永远不离开阿尔及利亚，1960年1月22日，他被召回巴黎并解除了一切军政职务。这一事件成了一场大动乱的导火索。
1月23日，国民议会代表皮埃尔·拉加亚尔德身穿伞兵制服，率领一群示威者占领了阿尔及尔大学大楼，其他示威者则由一个叫让—雅克·絮西尼的学生领袖率领，高呼“绞死戴高乐”，扒开街上的铺路石来设置街垒、路障，声称要坚持到马絮将军回到阿尔及尔为止。
就戴高乐好斗的性格来说，他是喜欢这种挑明了干的局势的。29日，他颇含深意地穿着准将制服，发表电视讲话，表明了自己愿意看到阿尔及利亚人自由地决定他们命运的态度，宣称在过去20年中，他一直体现了“国家的正统”，所以，“在不得已的时候，必须用武力恢复公共秩序。”
1月31日，经过一通宵谈判，叛乱分子投降了，拉加亚尔德·絮西尼等头领被捕并被用飞机送往巴黎受审。2月2日，国民议会通过一项法案，授予政府一年的特别处置权。接着，戴高乐改组了内阁，并在阿尔及尔开始了大刀阔斧且范围广泛的改革，包括重组警察，解散曾支持叛乱的本土防卫队，撤销主管心理战的国防部第五局，同时宣布大部分极端主义组织为非法。
制服了法国移民中的极端分子之后，还得制服军队里的反对势力。这股势力更强大更不好对付。戴高乐的对策是先极力做说服、软化工作，不到最后不摊牌。经过了长达10个月的缓冲时间后，他又走出了深思熟虑的一步：在11月4日的一次对全国的讲话中，他第一次使用了“阿尔及利亚共和国”一词，是颇有特色地用在否定它本身存在的上下文当中的。他说：他不能接受叛乱领导人提出的“阿尔及利亚共和国政府”的要求，这样的“共和国将来有一天会存在，但至今还从来没有存在过”。这种暗示性的讲话，使卷入阿尔及利亚事件中的各种力量进一步两极分化。
接着，按照既定战略，戴高乐决定就是否赋予阿尔及利亚自决权一事进行阿尔及利亚和法国本土的全民表决。为最后的结局铺平道路。1961年1月 8日举行的全民表决，清楚地表明了历史的趋势：本土76%、阿尔及利亚70%的选民赞成戴高乐的政策。
这就把军队内部的反对势力逼入了绝境，他们只能孤注一掷了。1961年4月22日，驻阿尔及尔的军官们发动了一场武装政变行动。军官们逮捕了一些行政官员，占领了主要公共建筑物，并且发表了文告，声称：“凡直接参与策划放弃阿尔及利亚和撒哈拉的任何个人，将被逮捕，并提交为审判危害国家安全罪而即将设立的军事法庭……”
这是对戴高乐权威的一次最大胆的挑战。戴高乐不无伤心地注意到，在策划和领导这场叛乱的五名上校和四名将军中，领头的竟是莫里斯·夏尔！戴高乐决定运用他的个人权威来面对这次挑战。为了使那些背叛的中级军官们有机会悔改，他派遣新任内务部长和国防部总参谋长冒着生命危险，于反叛文告发表几小时内到达阿尔及尔；同时，他行使宪法第16条赋予的特殊权力，切断了通往阿尔及利亚的一切海上和空中的交通，并宣布处于紧急状态。
接着，他让官方宣布，他将于4月23日晚8点发表电视演说。如同1960年1月那样，戴高乐将身穿两颗星的将军服（虽然按军衔来说比违抗他的人低）出现在屏幕上。他要以这样的视觉形象来提醒人们记住军事权威和军人服从的传统。
23日晚，他如期露面，态度强硬地谴责了这次叛乱。他说：“这样，国家受到愚弄，民族遭到藐视，我们政权不稳，我们的国际威望下降，我们在非洲的地位和作用受到损害。这是谁造成的呢？唉！是那些应该以其职责、荣誉和智慧来服务和服从的人所造成的！我以法兰西的名义命令，必须采取一切手段，我重复一遍——采取一切手段，布下天罗地网，直到把他们一网打尽。”
与1960年1月那次一样，戴高乐的个人魅力又发挥作用了。24日，叛方的势头开始减弱，军心动摇了。25日，曾支持过夏尔的军官们断定，他们是搞错了。下午，夏尔决定停止造反。第二天早上，他投降了。接着，另一位造反将军泽勒也投降了。剩下的萨朗、儒奥两位将军以及秘密军队组织的几位上校们一起转入了地下。
4月底，在阿尔及尔的内务部长和总参谋长宣布，有200名军官被捕，140名文官被停职，所有报纸被勒令停刊。5月底，军事法庭开庭，夏尔和泽勒被判15年徒刑，并被剥夺军衔和勋章，萨朗、儒奥和5名上校被缺席判处死刑。
这是以戴高乐获胜为结果的戴高乐与军内反对势力的第一次交锋。这以后，秘密军队组织转入地下，开始搞起消耗战，为所欲为地制造痛苦和流血事件。他们声称，他们的战略目的是：用使国家瘫痪的办法驱逐戴高乐，保持法属阿尔及利亚，从而避免它的领土沦入苏联共产主义者手中。为了达到这个目的，他们制订了极其残酷的工作方针：杀害“卖国贼”或仅为这个政权工作的人；破坏财产；迫害穆斯林，以便引发迫使军队出面镇压的群众暴动；暗杀戴高乐将军本人。
至少四次暗杀将军事件发生于1961年的9月和1962年的5月、6月和8月，但都失败了。第一次是因为出了技术故障，中间两次在布置就绪之前败露，最后一次则是出现了奇迹。1961年9月8日，谋杀者把装有90磅可塑炸药的煤气桶，里面还装有丁烷和一个储有汽油和肥皂片的罐头盒子埋在从巴黎到科龙贝的公路旁的沙滩里。晚上，当总统的汽车经过那里时，突然被一片火网包围了，但炸药却不知为何没响。1962年8月22日，在将军乘车前往库布莱镇军用机场的路上，一伙人从路旁的一辆黄色旅行汽车里向他的汽车开火。司机加速前进，但前行了100码，又遇上另一伙人从一条横街的一部蓝色汽车里开枪。谋杀者总共射击了约150发子弹，其中14发击中了戴高乐那辆特制的雪铁龙汽车，有两颗子弹击中了轮胎，但没有击穿；另一颗子弹击破了后窗，在离戴高乐头部两英寸的地方掠过，也没有造成伤害。停车后，戴高乐看看周围的人，感到了令人难以置信的侥幸。他不无幽默地咕哝道：
好，我们谁都没有中弹，那就让戴高乐继续走自己的道路，履行自己的职责吧！
他心目中的职责之一，就是使法国摆脱殖民包袱，首先让阿尔及利亚独立。在他的努力之下，法国政府代表和阿尔及利亚民族解放阵线从1961年5月20日起开始谈判，谈到第二年3月18日达成了停火以及通过全民表决决定实行自决之后“法阿”之间合作的协议。
1962年7月1日，阿尔及利亚举行全民表决，91. 8%的选民参加了投票，99. 7%的投票人赞成阿尔及利亚独立。这表明，戴高乐这位巨人，终于以他特有的眼光和毅力，圆满地完成了阿尔及利亚的非殖民化进程，完成了他顺乎历史潮流的一大壮举。
5 “开始实行我的宏大计划”
既然是世纪的巨人，就注定了他的内心是孤寂的，因为人的地位的梯级差距，法军的将军、上校们不可能像戴高乐一样能从全球的高度通观国际实力竞争格局，当然也就无法理解他被他的时代和地位赋予的“使法国重新具有伟大形象”的社会作用和个人理想。如果他们活到了80年代末，看到了西欧摆脱了“小伙伴”地位而与美国佬、小日本同为“世界三极”之一的社会现实，也许他们就会后悔30年前的所作所为了。当然这是“也许”。
任何社会现实都是一定经济实力的体现。当时西方各国之间的关系就是如此。二战结束后，美国实力空前增强。西欧各国则严重削弱。1947年6月5日，美国国务卿马歇尔提出《欧洲复兴方案》，即著名的“马歇尔计划”，这个计划共向西方各国提供了134亿美元，其中80%是无偿援助，从而从经济上控制了西欧各国，也就决定了西欧各国在政治上是美国的小伙伴关系。战前，西欧是世界政治中心。二战使德意志一败涂地，英法削弱；而战后民族解放运动的兴起，又使这些国家的实力进一步削弱。美国则一步步取代英法两大殖民帝国，实现了独霸。美国取得霸主地位、西欧成为小伙伴的标志，是1949年美国与西欧十国及加拿大签署的北大西洋公约——西欧各国置身于美国军事保护之下。
