与埃及国内轰轰烈烈的社会主义建设形成鲜明对比的是，这一时期埃及在阿拉伯世界受到多方攻击和冷落，处境十分孤立。它不仅同以前一样，同沙特、约旦和也门等国的国王们存在着尖锐对立，而且同从前的革命伙伴伊拉克也反目为仇，并与叙利亚分裂主义政权发生了公开冲突。此外，利比亚和摩洛哥的君主政体显然也无法博得纳赛尔的好感。唯一还能令纳赛尔感到些许欣慰的是：根据1962年3月的《埃维昂协议》，阿尔及利亚于7月3日摆脱法国正式宣布独立。由于第一任总统本·贝拉也反对帝国主义，信奉社会主义，主张奉行独立自主的不结盟外交政策，纳赛尔同他倒还合得来。由于叙利亚指责埃及干涉其内政（指埃及表示愿意同代表自由叙利亚人民的政府谈判走向联合的问题），并将这种指控提交阿拉伯联盟，联盟在黎巴嫩召开特别会议处理这一问题。埃及强硬地表示，如果联盟支持充当帝国主义走狗的叙利亚的卑劣行径，埃及将退出该联盟。可以想象，在这种孤立、紧张的处境下，纳赛尔作出支持也门革命者的决定，需要多么大的魄力。
1962年9月26日晚，一批少壮派军人在也门首都萨那发动政变，迅速夺取了政权，对外宣布：伊玛姆独裁统治已被推翻，共和国取代了神权君主国。应革命者的请求，纳赛尔向他们提供了革命援助。10月6日，第一批埃及军事专家飞抵也门，埃及军队也随后在也门登陆。这是纳赛尔直接动用武装力量，公开地支持别国内部革命的第一次行动。他是出于以下几点考虑：首先，这是一次将也门从野蛮、落后引向文明、进步的光明未来的革命。也门是阿拉伯世界最偏僻最落后的国家，就在它的近邻埃及，许多人甚至也是头一次听到这个国家。也门国王集王权、神权于一身，其腐朽程度到了猴子都懂得要反抗的程度。自1948年以来，也门就一直动荡不安，纳赛尔同那里的革命人士一直保持着直接或间接的联系（但并非像伊玛姆所说的那样，这次政变受到了纳赛尔的直接操纵）。其次，纳赛尔将也门革命看作是他的“阿拉伯革命”的一部分。纳赛尔一直就不甘心阿联的分裂，他期望着也门革命的成功能够使他摆脱孤立地位，甚至对阿拉伯半岛上的其他君主国家产生影响。再次，也门革命以摧枯拉朽之势控制了大部分地区，并且有消息称国王巴德尔已死，群龙无首。纳赛尔认为只要他再为革命者加一点儿力，即可大功告成。最后，这次革命受到了大部分阿拉伯国家的热烈欢迎，把它看作是阿拉伯半岛的第一场现代革命运动。由于也门的伊斯兰教长政权一贯臭名昭著，没有哪个进步政府愿意公开保护它，就连英美等西方大国驻也门的外交官也敦促各自政府承认新政权。既然如此，有什么理由能证明支援也门革命是错的呢？但纳赛尔万没料到，也门内战使他陷入了难以自拔的泥潭，就像美国在越南、苏联在阿富汗那样。
也门革命和纳赛尔的行动引起了阿拉伯各君主国、神权势力和酋长政权的惊恐。当他们得知伊玛姆并没有死，他已经逃到距沙特很近的山区，并收罗了几千人准备反攻时，好战的火焰翻腾起来。作为回击纳赛尔的手段，约旦和沙特联合起来，向隐藏在山区的伊玛姆残余势力提供了大批武器弹药、飞机大炮以及军事技术人员。纳赛尔的行动也受到了美英两国的敌视，尽管它们都对伊玛姆暴政不满，但美国担心也门革命会影响它在中东的石油利益；英国则担心自己在亚丁的军事存在受到打击，它那时正在筹备一个南阿拉伯半岛联邦计划，准备将亚丁和其他保护领地连结起来，掌握在英国手中。至于苏联，它愿意向革命派提供武器支持，期望也门革命能使美英等西方势力收缩回去，但它不愿卷入也门冲突，因为它发现革命派内部也分歧严重，这是由也门复杂的部族、教派冲突决定的。
由于残余势力受到西方和沙特、约旦等国的支持，也门革命并未像纳赛尔预料的那样迅速取得彻底的胜利，他不得不向也门提供更多的支援。可是，埃及也并不是什么富国，更何况此时还要进行国内社会主义建设呢？为了创造相对缓和的外部环境，纳赛尔开始寻求政治解决也门问题。在他的极力劝说下，也门革命政府宣布它将同所有邻国和平共处，继续履行国际条约所规定的国际义务，包括1934年英也两国条约在内的所有条约。纳赛尔的和平攻势取得了一定成效。1962年12月19日，美国承认了也门共和国，随后西德、意大利、加拿大、澳大利亚等国也作出了同样表示。英国虽然坚持在共和国政府控制了全部也门地区后再承认它，但保证不卷入也门内部事务。纳赛尔建议：在沙特和约旦对被推翻的伊玛姆的支持结束时，埃及愿意“采取”相应措施，迅速脱离接触，并分阶段从也门撤军。但是，“脱离接触”并未实现，沙特和约旦继续给予伊玛姆以军事支持。由于美沙特殊关系，以及1963年1月英沙恢复邦交，很难保证美英等西方国家在也门问题上持公正态度。
1963年初，也门内战局势明朗化：革命派和1.5万埃及士兵控制着广大的沿海平原，受到莎菲派教徒的支持；保王党势力控制着北部山区、东部沙漠以及萨纳周围的部分山区。2月底，埃及军队发动大规模进攻，准备捣毁保王党总部并切断保王党与外部联系的交通线。这次战役迫使保王党转入战略防御，但主要目标没有实现。此后，在联合国的调停下，战争时断时续。也门问题被拖延下来。
正当纳赛尔苦恼于国内建设与支持也门革命难以兼顾时，形势出现了某些对他有利的变化。1963年2月8日，伊拉克发生军事政变。与纳赛尔不和的卡西姆被杀，支持纳赛尔主义的阿莱夫成为新领导。3月，复兴党人和泛阿拉伯主义军官在叙利亚也发动政变，复兴党的地位壮大起来。叙利亚政变仅两天后，新伊拉克政府就建议：由五个“解放”了的阿拉伯国家（包括伊拉克、叙利亚、阿尔及利亚、埃及和也门）组建军事统一阵线。纳赛尔一直提倡的阿拉伯统一一时出现了曙光。
但是阿联的分裂对纳赛尔的打击太大了，至今他仍然把阿联的分裂归罪于那些复兴党人，因此对复兴党人的联合建议，纳赛尔不敢抱任何幻想。事实正是如此，复兴党人提出联合建议，主要是为了缓解持联合主义观念的新纳赛尔主义军官的压力，他们只想要一个未来联合国家的宣言以解除亲纳赛尔派的威胁，通过这个宣言，可以使叙、伊两国至少在二三年内自由活动。纳赛尔不仅怀疑这次联合的可能性，还担心联合的现实性，因为同伊拉克联合会加深同伊朗、土耳其、以色列以及西方大国的矛盾，也许还会卷入伊国内库尔德人和共产党人的叛乱，尽管如此，纳赛尔打算再试一试，联合毕竟是“所有阿拉伯人的希望，它在我内心深处”。纳赛尔这样描述联合的前景：“这个联合的国家将从油田通过输油管延伸到苏伊士运河，亦即说从亚洲延伸到非洲。这将使伊拉克军队列阵于以色列边界，其潜力也许比法国还要大，其人口将达到4000万。”
4月，埃及、叙利亚和伊拉克三国举行开罗谈判，商讨统一问题。三方就联合形式达成一致，决定建立联邦而非统一的中央集权主义国家。但在随后谈判诸如集体政治领导、联合军队、联邦宪法等实质性问题时，叙伊两国立场退却，它们要求在正式大选前有一段为期数年的过渡期，在此期间形成一种松散的联合。纳赛尔清楚，这样做并无太大意义，但只要朝着联合方向，不妨一试。4月17日，三方达成妥协，发表联合声明，宣布：建立在一位总统领导下的联合的埃及、叙利亚和伊拉克联邦国家；该联邦将成立一个以三个地区的民族阵线为基础的中央政治领导机构，制定一致同意的“联合宪章”和宪法；五个月内举行公民投票，选举总统，并批准宪法和政治宪章；二十个月内，联邦宪法将生效，举行议会选举，在此过渡期内维持松散的联合。
但好景不长，叙、伊两国复兴党同党外亲纳赛尔派及复兴党内的斗争加剧。在叙利亚，亲纳赛尔的联合主义者遭到清洗，主张“单干”的复兴党激进派占了上风，他们主张在左翼社会主义政府领导下，与伊拉克实现“没有纳赛尔”的联合。7月，清洗扩大。复兴党内反对与纳赛尔公开决裂的党员也被清洗，更激进的哈菲兹将军接管政权，并对联合主义者进行了残酷的镇压。纳赛尔对在叙利亚发生的大清洗极其震惊与愤怒，这意味着四月协定已成一纸空文。5月17日，纳赛尔宣布他已不能同复兴党人共存或合作。7月22日，纳赛尔在开罗发表演说，猛烈抨击在大马士革掌权的复兴党人是“法西斯主义分子、机会主义者、分离主义分子”，并宣布埃及不再受联邦协定的约束。
伊拉克总统阿莱夫试图调解埃叙两国冲突，挽救联邦协定的命运，但未获成功。9月，伊叙两国就经济和军事合作达成协议，组成了开罗协定中设计的联邦。10月7日，两国军队实现联合。但不久，更激进的复兴党派别在叙利亚强烈要求极左的“新计划”，导致叙伊联盟出现裂痕。11月中旬，伊拉克内部发生动乱，阿莱夫动用武力，强行接管了全部政权。
1963年底，中东形势一片大乱。埃叙两国再次相互攻击，伊拉克爆发内乱，也门战火又起，阿尔及利亚和摩洛哥因国边界纠纷发生武装冲突，塞浦路斯爆发内战等。此外，以色列的约旦河上游河水改道工程即将完成，使阿以争端在经历了七年相对平静的时期后，再度紧张。面对第二次联合的失败和复杂多变的中东局势，纳赛尔准备调整其阿拉伯政策，使阿拉伯国家从内部争吵中解脱出来，共同对付以色列这一阿拉伯世界的敌人。
1963年12月23日，纳赛尔发出召开阿拉伯联盟首脑会议的号召。并作出和解表示，主动停止了对主要阿拉伯对手（例如沙特和约旦的国王、哈菲兹将军、哈桑国王等）的攻击性宣传活动。在埃及的大力推动下，第一次阿拉伯国家首脑会议于1964年1月13日至17日在开罗举行。纳赛尔在会上介绍了他未来若干年内的基本政策，即追求阿拉伯国家的“共存”和调整埃及的政治与经济体制。他表示放弃过去只有信奉社会主义并反对帝国主义的阿拉伯国家才能与埃及密切合作的观点，提出：只要不敌视埃及，无论意识形态如何，合作都可以在阿拉伯联盟的框架内得到解决。今后埃及外交主要努力方向是促成也门问题尽早和平解决和采取一种针对以色列的谨慎的阿拉伯联合政策。
在纳赛尔的努力下，埃及同约旦、伊拉克的关系得到了一定改善。1964年6月，约旦承认了也门共和国。12月，纳赛尔和阿莱夫达成了关于埃伊“联合政治领导”的协议，商定两国政府将定期进行政治协商。必须看到，中东地区始终是多事之地，纳赛尔的外交努力并不能一下子消除阿拉伯国家间的许多固有矛盾。例如，埃及同沙特之间的关系时缓时紧；纳赛尔同叙利亚复兴党政府一直失和；由于他的好友本·贝拉1965年6月被军事政党推翻，埃及同阿尔及利亚的关系也冷淡下来等。
在开罗首脑会议上，纳赛尔和沙特领导人就也门问题进行了谈判，虽然双方立场相距甚远，但已显露出和解迹象。沙特也感到无力长时间在也门问题上打消耗战。3月，埃沙两国恢复外交关系，宣布双方均对也门没有政治野心。考虑到也门革命阵营开始分裂，反对埃及军事存在的“第三势力”上升，纳赛尔在4月对也门的访问中，竭力劝说共和国政府同保王党人和平谈判，前提是保持埃也两国友好关系，埃军体面地撤出也门。
1964年9月，第二次阿拉伯首脑会议在亚历山大召开。纳赛尔同沙特国王费萨尔就也门问题进行谈判，取得积极进展。在埃沙两国的敦促下，也门交战双方于11月2日在苏丹的埃雷克威特举行秘密会议。双方达成停火协议，并商定于23日前举行由也门各派代表参加的政治协商会议，以讨论建立一个联合民族政府的问题。但由于双方对与会者和议程意见相反，政协会议未能召开。会议流产，导致双方不信任加强，也门局势再度紧张。
长时间的军事僵持，谁也无法取得绝对性胜利。为了打赢这场战争，埃及投入了几千万英镑，数千名埃及士兵死在沙场。由于资金匮乏，已使埃及国内的五年计划无法顺利完成，使埃及背上了沉重的债务负担。人民的不满情绪上涨。面对如此严峻的形势，纳赛尔同费萨尔国王秘密地进行了吉达会谈。急于从也门内战中脱身的共同心理使他们很快达成了一项新的和平协议。除了再次确认停火和召开政治协商会议的原则外，该协议规定：埃及将从1965年11月23日开始的10个月内从也门撤完军队；沙特停止向保王党人提供所有形式的援助并停止用其领土支援也门的军事行动，在埃军撤出后两个月，即1966年11月23日前举行全民公决以确定也门未来的政府形式，由保王党人和共和主义者共选出50人，商讨全民公决前过渡政权和临时政府问题。
按照埃沙两国的和平协定，也门交战双方于1965年11月23日举行哈拉德会议。由于也门人内部积怨太深，以至在过渡政府称谓上谁也不肯让步。一个多月过去了，谈判仍无法突破僵局。也门人的互不信任再一次影响了埃沙两国的态度。沙特对埃军按兵不动表示怀疑，埃及则对沙特从英国购买飞机，从美国购买导弹的作法表示不安。
针对也门的“冷和平”局势及英美企图发挥更大作用的倾向，纳赛尔对也门共和国控制的区域采取了“防御性控制”战略，进攻目标间接地指向沙特人、英国人、保王党人及英国的势力范围——南阿拉伯半岛和亚丁。这一战略包含四方面内容：一是将共和主义者和埃及人控制的地区收缩到“中央设防区”，该区域包括了也门大多数人口和主要城市。二是支持一个值得信赖并接受埃及人存在的强大的共和国政府。三是继续巩固革命政权，通过经济和社会援助，扩大埃及影响。四是阻止保王党人的进攻，必要时发动强有力的军事进攻。这一战略表明了埃及将不得不在也门再消耗一些元气。
1967年6月，埃及惨败于以色列之手。除了战略收缩外，纳赛尔别无选择。8月底，在喀土穆举行的阿拉伯首脑会议上，纳赛尔同费萨尔达成了埃军年底前从也门全部撤军的决议，由苏丹总理、伊拉克代理外长和摩洛哥外交大臣组成阿拉伯三方委员会负责组织交战双方的和平会谈。共和主义者立即指责这是埃及对也门的出卖。此后，沙特也切断了它对保王党人的援助。也门在打打停停了一段时间后，在保王党人承认共和的基础上，交战双方达成政治妥协，不久，沙特正式承认了也门共和国。
从1962年9月至1969年底也门内战整整持续了七年多的时间。按1967年底埃军撤离算，埃及卷入也门内战进退维谷、无法自拔达五年之久。若把此时期消耗的巨大人力物力投入于国内建设，埃及恐怕不会被以色列打得那么惨。但是，纳赛尔的立场是毋庸置疑的，他的“阿拉伯革命”的思想不允许他对也门革命袖手旁观。值得欣慰的是，也门的共和政体保住了，没有埃及的援助，也门革命就不可能成功，也门就不可能摆脱愚昧落后的状态。也门内战和围绕着它进行的外交斗争，再次证明了阿拉伯世界的关系复杂纷繁。中东的巨大能量和它那狭小的空间决定了爆炸是常有的事。
