7月17日，柬埔寨政府召开最高国防会议和内阁会议，决定承认中华人民共和国。18日，西哈努克致函周恩来，提出两国正式建立大使级外交关系的建议。次日，周恩来复函西哈努克，同意和柬埔寨建交并表示中国将尽力支持柬埔寨维护独立主权、反对外来侵略的斗争。王幼平被任命为中国首任驻柬埔寨大使。在他去柬埔寨赴任之前。毛泽东对他说，不要在柬埔寨宣传社会主义和共产主义。周恩来特别叮嘱王幼平“一定要交好西哈努克这个朋友”。
美国官员对西哈努克同中国建交的决定极度恼火。美国驻柬埔寨大使卡尔·斯特罗姆（Carl W.Strom）于7月25日约见西哈努克，谈柬埔寨承认中华人民共和国的问题。斯特罗姆抱怨，在过去两年中，美国和柬埔寨之间一直存在着“尖锐的政策分歧”，西哈努克承认中华人民共和国的决定是一个“重大政策转变”，它不仅将柬埔寨置于苏联和中国“新殖民主义”的威胁之下，还使柬埔寨的邻居也处于共产主义颠覆的危险之下。东南亚条约组织的成员都批评柬埔寨，柬埔寨没什么朋友，是孤家寡人。斯特罗姆要西哈努克和南越搞好关系，西哈努克先为他的中国政策辩护，强调中国是柬埔寨旁边的一个大国，是一个现实存在。在对待分裂国家的问题上，他过去两年中一直采取不偏不倚，“一律看待”的立场，但这个政策并不成功。实际上，从万隆会议以后，他就一直在考虑承认中华人民共和国的问题。在谈到柬埔寨和南越关系的问题时，西哈努克说，尽管法国殖民时期划定的柬越边界对越南有利，但是越南人还不满意，他们老是要蚕食柬埔寨领土。他告诉斯特罗姆，在柬埔寨人眼里，越南人比中国人更危险。斯特罗姆对西哈努克的失望之情，溢于言表。
在和美国打交道的过程中，西哈努克越来越感到美国人的骄横和美援条件的苛刻。在柬埔寨的美国外交官经常颐指气使，美国大使甚至穿着短裤去和柬埔寨人会谈。美国提供的经济援助只能用于私营企业，不能用于国营企业，而在柬埔寨经济中，既有私营企业，又有国营企业。美国人规定，柬埔寨既然接受美国的军事援助，就不应该再接受社会主义国家的军事援助。
而中国领导人对柬埔寨却一直很耐心和友善。1958年7月24日，周恩来在和柬埔寨驻华经济代表团团长杨安讨论中柬关系问题时说，中国非常了解和同情西哈努克亲王处境的困难，所以尽量给予支持，希望帮助柬埔寨克服这些困难。亲王对美国采取强硬的态度是适当的。在谈到经济援助问题时，周恩来说，中国在发展中，以后不仅在道义上，在物质上也可以多给帮助。现在我们正在发展工业，也希望别的国家发展工业，使亚非国家都强盛起来。我们愿意把中国的建设经验介绍给友好国家，愿帮助它们用最新的技术、最低的成本、最少的劳动力、最快的速度来进行建设。
8月15-25日，西哈努克率柬埔寨王国国家代表团对中国进行第二次正式访问，会见了毛泽东和周恩来。在周恩来的陪同下，西哈努克还去东北和天津访问，并参观中国第一座实验性原子能反应堆和回旋加速器。访问结束时，双方签署《周恩来总理和西哈努克首相联合声明》。声明指出，双方对中柬建交、发展经济和文化关系、中国侨民和柬埔寨人民友好相处等表示满意。声明还强调，柬埔寨奉行的和平中立政策应该得到一切国家的尊重，民族独立运动是当前时代不可抗拒的潮流，一切国际争端应该根据和平共处原则通过和平谈判求得解决。西哈努克后来在他的《回忆录》中写道，毛泽东很关心柬埔寨的国内情况，很关心柬埔寨同邻国的关系，很想知道他对美国的亚洲政策的看法。西哈努克觉得，毛泽东是以平等的态度对待他的，不像有些西方国家领导人（除了戴高乐将军）那样傲慢。
西哈努克回到金边后，和美国大使斯特罗姆谈了他的中国之行。他告诉斯特罗姆，他在北京访问时，中国方面表示愿意向柬埔寨提供军事援助和进一步的经济援助，但他只接受了中国的进一步的经济援助，而没有要中国的军事援助，因为他对目前从美国和法国那里获得的军事援助感到满意，他不能同时接受两边的军事援助。他还对斯特罗姆说，柬埔寨的外交政策没有改变。但斯特罗姆不相信他的话，反唇相讥地说：“柬埔寨宣布支持联合国接纳红色中国就代表了一个政策变化。”
西哈努克对斯特罗姆说的话很能反映此时他对美国的复杂心理：一方面，他知道美国人对他和中国建交并再次访问中国的举动不满，所以他对斯特罗姆说，柬埔寨的外交政策没有改变，以打消美国的猜忌和疑虑。尽管他不满美国在柬埔寨和南越、泰国的领土争端问题上不支持他，但他也不愿意和美国翻脸，仍想维持和美国的关系。另一方面，他也想告诉美国人，柬埔寨并不完全依赖美国，如果美国不给柬埔寨军事援助，他可以从中国那里获得，所以美国应该多和柬埔寨合作，特别是在柬埔寨和南越、泰国的领土纠纷问题上，否则，他可能更倒向中国。
美国军方一直很担心西哈努克会向中国要求军事援助。8月22日，美国参谋长联席会议在一份给国防部长尼尔·麦克艾尔罗易（Neil McElroy）的备忘录中指出，中国可能以中柬建交为契机，试图向柬埔寨派遣军事援助人员，美国应该“采取新措施以阻止柬埔寨滑向一个更容易被共产主义颠覆和控制的处境”。参谋长联席会议建议，美国应该加强和柬埔寨军队的联系，依靠柬埔寨亲西方的军队领导人，来抗衡那些主张和共产主义国家改善关系的柬埔寨政治势力。1959年，美国邀请柬埔寨军方派人去菲律宾参加东南亚条约组织的海军演习，柬埔寨军队中的一些高级将领，比如武装部队总参谋长朗诺（Lon Nol）和国防大臣涅·刁龙（Nhiek Tioulong），主张派观察员去参加，但遭到西哈努克和外交部长宋双（Son Sann）的反对，未果。尽管朗诺和刁龙这样的高级将领有亲美倾向，但西哈努克此时在柬埔寨享有很高威望，还是能够驾驭他们的。发生在1959年的达春事件（Dap Chhuon Plot）加深了西哈努克对美国的不信任。达春是柬埔寨暹粒（Siem Reap）省省长和西北军区司令员，长期拥兵自重，野心勃勃，在暹粒省搞独立王国，还想将暹粒省从柬埔寨分离出去。他批评西哈努克的中立外交政策，反对柬埔寨同中国建交。他和流亡国外的西哈努克政敌山玉成（Son Ngoc Thanh）暗通款曲，并通过山玉成与南越和泰国建立了联系。南越和泰国则视达春为推翻西哈努克的工具，不但给他武器，还向他提供广播设备，供他作反对西哈努克宣传用。2月21日，西哈努克先下手为强，派兵攻占暹粒，达春畏罪逃跑。3月3日，他在试图穿越边界向泰国逃窜时，被朗诺将军带领的军队击毙。美国中央情报局究竟在多大程度上卷入达春事件仍是一个谜，但有一点很清楚，就是美国官员是事先知道达春想谋反的，而且没有将他要政变的情报告诉西哈努克。实际上，从柬埔寨和中国建交以后，不少美国官员就已经不看好西哈努克了，转而暗中支持柬埔寨反对西哈努克的组织和个人。
中柬《友好和互不侵犯条约》的签订
1959年以后，柬埔寨的安全形势更趋严峻。在南越，反对吴庭艳政权的武装运动日益发展。由于为南越的共产党武装运送人员和武器装备的秘密运输线（即“胡志明小道”）是从柬埔寨领土经过，所以，吴庭艳的军队在美国的支持下加大了对柬埔寨的袭击，侵犯柬埔寨的领空和领土，试图切断南越游击队的补给线。此外，南越还向柬埔寨提出几个沿海岛屿的领土要求。
为了表示对西哈努克的支持，周恩来和陈毅于1960年5月5日至9日正式访问柬埔寨。由于周恩来访柬时正值柬埔寨为已故国王苏拉玛里特举行国丧，所以周恩来及代表团全体成员是穿着素白礼服到达金边波成东机场的。到达金边后不久，周恩来就去向苏拉玛里特的遗体致哀。6日，在高棉皇家社会主义青年团组织的欢迎大会上，周恩来说：“我可以向你们保证，在你们和全体柬埔寨人民为保卫民族独立而进行斗争的时候，你们可以指望六亿五千万中国人民始终不懈的支持。”在访问结束时，双方发表了联合声明，其中特别提到，双方谴责任何用武力侵犯邻国的企图。
次日，周恩来在西哈努克的陪同下，在金边主持柬埔寨皇家电台开幕式，这个电台是周恩来在上次访问柬埔寨时赠送给西哈努克的礼物。周恩来还参观中国援建的胶合板厂并接见200名华侨代表。周恩来向华侨代表询问了在柬埔寨生活和工作的华侨的情况，指出柬埔寨对华侨的友好政策，可以作为东南亚国家对华侨政策的一个范例。他嘱咐华侨要尊重柬埔寨法律，学好柬埔寨语言，在投资方面多发展对柬埔寨国计民生有利的工业，搞好同柬埔寨人民的关系。
8日，周恩来、陈毅同西哈努克一块，乘柬埔寨海军的一艘巡逻艇游览南部风景名城白马（Kep）湾，在巡逻艇驶过的海域中，有一些星罗棋布的岛屿。在巡逻艇甲板上，西哈努克告诉周恩来和陈毅，不久前南越海军曾在五个岛上登陆，经柬埔寨政府发表严正声明，如果南越海军强行占据这些岛屿，就意味着同柬埔寨开战，柬埔寨将宣战，后来南越海军才不得不从五个岛屿撤走。周恩来和陈毅在柬埔寨海军船只上远眺曾被南越海军强占的岛屿，表明了中国政府对柬埔寨维护领土主权斗争的坚定支持。
西哈努克此时尽管对美国政策不满，但他也不愿意得罪美国。在周恩来和陈毅访问柬埔寨以后不久，西哈努克于6月对英国官员马尔科姆·麦克唐纳（Malcolm Macdonald）说，他将在不久的将来去北京签订一个友好条约，但他和中国改善关系并不意味着他敌视西方或支持共产主义。柬埔寨人之所以对中国有好感，一方面是因为他们中很多人有中国血统，另一方面是因为中国对柬埔寨总是抱持友好合作的态度。他要麦克唐纳转告美国人，虽然南越和泰国觊觎柬埔寨领土，但他还不打算从苏联或中国那里获得军事援助。西哈努克暗示，如果南越和泰国继续向柬埔寨施加压力，他可能会和中国签订一个保证柬埔寨边界安全的条约。
三个月以后，西哈努克在纽约出席联合国大会期间，同美国总统艾森豪威尔见了面。在谈话中，西哈努克告诉艾森豪威尔，最近越过边界进入柬埔寨的南越人日益增多，这些南越人中有不少是同南越政府对着干的叛乱分子。柬埔寨需要一些飞机和运输车来加强边界防卫。
12月中旬，西哈努克再度访问北京，寻求与中国的进一步合作。他和中国领导人讨论了签署中柬《友好和互不侵犯条约》的问题。中方准备的条约原稿中有“和平共处五项原则”八个字，但在柬埔寨提出的对案中，这八个字被删去，原因是柬埔寨听西方通讯社说，中苏在这个问题上有分歧，苏联赞成和平共处，而中国不赞成。在谈判中，中方表示希望条约仍包含“和平共处五项原则”字样，柬埔寨最后表示同意。条约第四条明确规定：缔约双方保证互不侵犯，不参加针对另一方的军事同盟。这样，柬埔寨就在法律上保证不会参加东南亚条约组织。
在华期间，西哈努克除了缔结中柬《友好和互不侵犯条约》外，还和周恩来就进一步发展柬中经济技术合作的问题进行了会谈。他们主要讨论了原来援助柬埔寨的四个项目要增加设备、建设钢铁厂和机械厂需签订具体协议、修建铁路的技术帮助、帮助勘察铁路线路等问题。周恩来向西哈努克了解柬埔寨的农业情况，说以便考虑派什么样的技术人员去柬埔寨提供帮助。
美国官员非常关注西哈努克是不是开始从中国获得军事援助。美国驻柬埔寨大使威廉·琼布（William Trimble）在向国务院报告西哈努克访华情况时说，尽管中柬联合公报和中柬领导人的公开讲话都没有提及中国向柬埔寨提供军事援助的问题，但不排除双方私下签订了有关军援的秘密协定。琼布认为，西哈努克在处理同中国和美国的关系时，并没有一碗水端平，因为他同意成立柬中友好协会，而迟迟不成立柬美友好协会。
在这一时期，西哈努克除了加强和中国的合作以外，也努力改善同其他社会主义国家的关系。他在访问中国之前，还访问了苏联和捷克斯洛伐克。苏联同意帮助柬埔寨建立一所技术学校，修建水电站和探矿。西哈努克邀请苏联领导人赫鲁晓夫访问柬埔寨，并开始派学生去苏联、东德等东欧国家学习。中柬《友好和互不侵犯条约》的签订进一步巩固了中柬友好关系，为两国在1960年代前半期的多方面合作打下了坚实的基础。
中柬在国际事务中的合作
1960年代上半期，中柬两国在一系列国际问题上互相协调，互相支持。这些问题包括：老挝危机、中印边界冲突、中华人民共和国在联合国的代表权，核武器和核试验等。两国关系在国际事务的合作中得到进一步发展。