1950年代后期，中国政府在考虑和什么样的法国政治团体与个人发展关系时，往往先征询法共的意见，以免中国的举动会损害法共在国内的政治地位。特别是在1958年的选举中，戴高乐处心积虑地打击法共，收效显着，法共获得不到百分之二十的选票，只有10名法共成员被选进法国国民议会。这是法共在历次选举中表现最差的一次，而在1956年的选举中，有150名法共成员当选为国民议会议员。鉴于法共在国民议会中影响力的下降，法共领导人不得不调整议会斗争策略，把注意力更多地放在组织街头行动和工厂罢工上。
1958年中国外交部对法国国民议会议员贡特（A.Conte）要求访华一事所做的反应充分地说明了中方要保护法共的意愿。贡特是法国国民议会中的社会党议员。1958年，在他的倡议下，国民议会重新成立“扩大同中华人民共和国经济和文化关系研究组”，由他任主席。同年6月16日，贡特到中国驻瑞士大使馆，会见冯铉大使，要求8月访华，称他希望同中国政府讨论中法关系问题，返法后将向戴高乐汇报讨论情况，以便戴高乐“作出重大政治决定”。他告诉冯铉，他在来瑞士之前曾见到外交部长顾夫·德姆维尔（Couve de Murville）和总理办公厅主任，并且他将在下个月参加在斯特拉斯堡举行的欧洲理事会上提出动议，建议所有欧洲国家承认中国。贡特还表示，他将在报纸上发表呼吁承认中国的文章。至于他为什么急于要在8月访华，贡特解释说，9月法国要举行修改宪法公民投票，所有政治人物都将为此活动和奔忙，所以8月以后他就没有时间去中国了。
冯铉向贡特阐明中国政府对承认问题的态度和立场，并问法国将如何承认中国。贡特答称，一切问题由戴高乐本人决定。贡特虽然表示“不能承认‘两个中国’”，但又说：法国没有正式理由同台湾断交，而希望在法国承认中国后，台湾能主动同法国断交。冯铉在给外交部的汇报中谈了他对贡特的印象：此人“极端反动，坚决反共，支持戴高乐”。估计他要求访华的目的是“在中国问题上取得政治资本和以此问题作为社会党和戴高乐关系中的桥梁，同时通过此次访问，了解我国态度，为戴准备在9月底法公民表决前打出一张外交政策的牌位”。冯铉建议：为了不让贡特获得政治资本，“可暂拖延一时，推迟其行期，待确知戴本人意见后再考虑具体答复。妥否，请速示”。
外交部在给驻瑞士大使馆的回电中，同意冯铉对贡特要求访华动机的分析，并就如何答复贡特作了指示。外交部的电文指出：“修改宪法公民表决是目前法政治中心，戴高乐派为了击败法共，争取表决胜利，正试图利用中法关系作为骗取选票的手段之一。估计戴目前不可能满足我方条件，而且为了免于被动，可能在公民表决前不作明确表示，但将要求和我国进行某种官方或非官方的接触，进行承认中国的笼统宣传。”外交部指示驻瑞士大使馆：“我们对戴高乐政府以及法资产阶级人士此类试探的处理，必须遵循下列原则：（1）我反对美英制造‘两个中国’的立场必须明确，不容模糊；（2）不能让戴高乐政府利用中国问题欺骗人民，打击法共；（3）在有利条件下利用法美在中国问题上的矛盾，打击美国。”
中国领导人明白，法国共产党在殖民地独立问题上处于一种尴尬的境地：从道义上说，法共应遵循反对殖民主义的原则；但从国内政治角度看，如果法共大张旗鼓地公开赞同法属殖民地的独立运动，它在国内选举中就可能失去很多选票。阿尔及利亚问题就是一个例子。阿尔及利亚民族解放斗争在1950年代后期迅速发展。1958年，阿尔及利亚解放军已经控制了阿尔及利亚国土的三分之二，建立了自己的根据地，掌握了十几万军队。阿尔及利亚解放阵线于同年9月19日宣布成立临时政府。中国政府不顾法国外交部宣称任何国家承认该临时政府都将被法国政府视为“不友好的举动”，继一些阿拉伯国家之后，于9月22日成为第一个承认阿尔及利亚临时政府的非阿拉伯国家。在积极支持阿尔及利亚独立运动的同时，中国领导人也建议他们谅解法国共产党不愿立即和直接表示支持他们的苦衷。1959年5月2日，陈毅在接见由奥马尔·乌西迪克率领的阿尔及利亚军事代表团时说，法国共产党“是支持亚非人民的反帝斗争，也支持你们摆脱从法国殖民主义统治的，从原则上看这不成为一个问题”，但是，“为了争取选票”，法共不便“立即和明确地支持殖民地国家的独立斗争，他们往往采取另一种态度”。
实际上，在1950年代后期，对于戴高乐政府而言，打承认中国的牌，不仅是为了在国内政治中削弱法共的影响力，还是为了减轻法国在阿尔及利亚战争中所受到的压力。1959年7月，法国政府向中国试探：如果法国放弃台湾，中国是否可以在援助阿尔及利亚问题上做些让步，以打开中法关系。7月17日，法国国民议会内属于戴高乐派的新共和联盟议员德洛纳（Dronne）找新华社驻巴黎记者陈定民谈话，强调戴高乐奉行独立的外交政策，不倚赖和追随美国，因此承认中国的可能性很大，但把承认中国没有进展的原因归咎于中国支持阿尔及利亚临时政府和对阿尔及利亚民族解放阵线提供援助。在涉及台湾问题时，德洛纳用东西德国和南北朝鲜相类比。中国外交部在获悉德洛纳的谈话后，给国务院外事办公室写了一个报告，分析了德洛纳谈话的背景。外交部的报告指出：“德洛纳此次约我记者谈话一定程度上是法政府的授意。我们估计其主要目的有二：（1）企图在联合国大会前夕，利用‘承认中国’的姿态来要挟美国在阿尔及利亚问题上支持法国。（2）妄图以‘承认’我国诱使我放缓对阿尔及利亚民族解放运动的支持和离间我和阿人民的关系。”对于如何回应德洛纳，外交部提出四点建议：“（1）德洛纳如再找我记者，仍可保持接触，以便继续了解法对我政策的动向，但我目前不去主动找他，以免造成我对法‘承认’有兴趣的迹象。（2）在谈到阿尔及利亚问题时仍应保持鲜明的正义立场，不给他以任何离间的余地。（3）说明台湾问题和东西德、南北朝鲜是不同性质的问题，坚决反对其‘两个中国’的谬论。（4）指出和台湾保持关系便是对中华人民共和国的敌视，这种状况不改变，中法关系的正常化便无从谈起。”国务院外事办公室主任陈毅在看了外交部的报告后，对外交部的分析和建议表示同意，并在报告上画了圈。
1959年，联合国大会讨论“西藏”问题时，法国投了弃权票，采取了和美英两国不同的立场。在中印边境冲突问题上，法国的态度与美英也不相同，并未公开攻击中国。
1960年5月27日，毛泽东在和来访的英国蒙哥马利元帅（Field Marshal Bernard Montgomery）谈话时，再次对戴高乐作出正反两方面的评价：既赞扬他抵制美国的做法，又批评他不放弃阿尔及利亚战争。毛泽东说：“我们对戴高乐有两方面的感觉：第一，他还不错；第二，他有缺点。说他还不错是因为他有勇气同美国闹独立性，他不完全听美国的指挥棒，他不准美国在法国建立空军基地，他的陆军也由他指挥而不是由美国指挥。法国在地中海的舰队原来由美国指挥，现在他也把指挥权收回了。这几点我们都很欣赏。另一方面他的缺点很大。他把他的军队的一半放在阿尔及利亚进行战争，使他的手脚被捆住了。”
1960年9-10月间，正在努力摆脱法国殖民统治的阿尔及利亚临时政府总理菲尔哈特·阿巴斯（Ferhat Abbas）率代表团访问中国，受到毛泽东和周恩来的接见和鼓励。9月30日，阿巴斯在和毛泽东谈话时曾担心地问：“我们读你的军事书，利用你的战法，如果法国人也读你的军事书，利用你的战法怎么办？”毛泽东充满信心地回答：“我根据中国经验写的书，只适用于人民战争，不适用于反人民的战争，强大的侵略军队不可能因为看了我的书而能够挽救他们的失败。”话题转向中法关系，毛泽东提出中法建交的两个前提条件：“一个是要它同蒋介石断绝外交关系，一个是不能干涉我们对你们的援助，如果把干涉我们对你们的援助当作建交条件，我们决不干。”
10月3日，周恩来在和阿巴斯会谈时，解释武装斗争和外交斗争的关系。周恩来说：你们在决不放下武器、坚持武装斗争的同时，不排除通过平等谈判来进行争取民族独立的政治斗争的方针是正确的。外交斗争是政治斗争的一个部分。武装斗争和外交斗争应有主从，我们认为，应该以武装斗争为主，外交斗争是配合武装斗争的。戴高乐所以要同你们谈判，正是因为你们始终坚持着武装斗争。所以，武装斗争是基础，没有武装斗争，外交斗争将软弱无力。
1961年2月，法国社会党参议员、民主社会抵抗联盟主席弗朗索瓦·密特朗（Francois Mitterrand）访华时提出：“中法建交必须在阿尔及利亚问题解决之后，”暗示只要中方停止对阿尔及利亚民族解放斗争的援助，中法就可以建立外交关系。陈毅外长明确地回答说：“中国承认阿尔及利亚临时政府，并不是去搞掉法国，你占领阿尔及利亚。中国不能拒绝穷民族援助的要求、搞外交关系的要求。”“我们过去自己受压迫，中国自己不援助被压迫民族，脸上无光。”毛泽东在和密特朗交谈时，也强调中国不会为了中法建交而放弃对阿尔及利亚民族解放斗争的支持：“阿尔及利亚问题是阿法双方的事，应由阿法双方谈判解决；解决阿问题首先要给阿独立，并撤出全部占领军；中法总是要建立外交关系的，但要在阿尔及利亚问题解决之后。”毛泽东和陈毅的讲话清楚地表明：中国可以把中法建交问题放一放，但是援助民族独立斗争义不容辞，事关原则大事，中国是不会拿原则做交易的。
尽管阿尔及利亚问题使中法关系难有重大突破，但中国方面在国际场合仍密切关注美法矛盾的发展，对美国和法国区别对待。1961年2月，法国驻柬埔寨大使皮埃尔·高斯（Pierre Gorce）即将卸任回国。驻金边外国使团团长英国大使提议：以外国使团名义，为高斯大使举行欢送酒会，并向他赠送一个刻有各国大使名字的银盘。英国大使宴请中国大使馆参加。中国大使馆向中国外交部请示是否可以参加。外交部西欧司和礼宾司都不反对。在给驻柬埔寨大使馆的回复中，外交部指示：“考虑法国大使一般对我尚友好”和法美在柬埔寨的矛盾等情况，“同意你馆参加使团为法大使举行的告别酒会和集体送纪念品。”
1960年代初，一连串的国际形势发展使中法关系正常化的条件日趋成熟。1961年5月，关于老挝问题的日内瓦会议召开。在会议上，中国采取分化英、法、加拿大同美国关系的方针，孤立美国，克服主要来自美国的阻力，使会议达成有关老挝中立的协议。陈毅外长和法国外交部长德姆维尔商谈了两国关系正常化问题。德姆维尔表示：目前建交还有困难，希望先加强贸易和文化方面的交往。此后，法国开始逐渐疏远与台湾的关系，冷淡台湾派往巴黎的官员。戴高乐政府采取措施发展对华经济和文化关系，为建交创造条件。
1962年2月，法国和阿尔及利亚签署了《埃维昂协议》，结束阿尔及利亚战争，使得中法关系发展道路上一个主要路障被扫除。从1962年6月起，《人民日报》不再发表攻击戴高乐政策的文章。该报在当年6月5日报道法国选出新国民议会时，以中性的用语说：“戴高乐派及其支持者占绝大多数席位。”而在四年前，中国报刊在评论戴高乐上台后新选出的国民议会时，批评的语调十分明显，批评戴高乐策划的所谓“议会选举”是“摧残民主”。四年之中，中国官方媒体对法国两次国民议会选举的不同评价，清楚地表明中国领导人对戴高乐的看法已发生了很大的变化。
由于法共在中苏分歧中支持苏联，中国领导人在制定对法政策时已不再顾及法共的利益，已不再担心发展中法关系会对法共造成不利影响。中共后来甚至考虑用改善同戴高乐政府的关系来打击法共。1962年2月21日，廖承志在全国外事工作会议上分析各国共产党的情况时说：“英共和法共不像共产党，简直是社会党。某些资产阶级左派做的事反而像共产党，他们有阶级分析。美共、西欧、北欧共产党，好的已没有几个。美、英、法、意、比利时等国的共产党都不行，领导人是工人贵族为基础的修正主义者。”在非洲，“挂共产党招牌的不像共产党。阿尔及利亚共产党打游击时看不见，和法国谈判就出来了。摩洛哥、突尼斯、苏丹、黎巴嫩共产党都是扯淡的。这些党已成为革命的绊脚石，大部分是法共搞起来的，不少是拿美国的津贴”。
1963年7月，美国、英国和苏联签订部分禁止核试验条约，力图阻止中国和法国通过一般核试验来建立自己的核力量，中法在反对超级大国控制世界的问题上又增加了一个共同点。与此同时，中苏关系进一步恶化，美国对印度支那事务的干涉越来越深，再次与法国在该地区的利益相矛盾。
