1958年，陈毅以副总理身份兼任外长。任职期间，他非常重视对非工作，除了热情接待到访的非洲代表团和友好人士，还多次前往非洲访问。1963年12月上旬，陈毅赴肯尼亚参加盛大的独立庆典。并直接从内罗毕飞往开罗，陪同周恩来总理首次访问非洲十国；1964年11月他访问阿尔及利亚和阿联；1965年6月，赴阿尔及利亚参加第二次亚非会议外长预备会议；1965年9月访问阿尔及利亚、马里和几内亚。陈毅是我国第一代领导人中涉足非洲次数最多的一位，在与非洲国家交往中，展现了一位无产阶级政治家和元帅外交家的崇高胸怀和豪爽性格，与非洲人民结下了深厚情谊，赢得了非洲人民的钦佩和赞扬，为中非友好关系的发展作出了卓越贡献。
1963年12月至1964年2月，周恩来总理在陈毅副总理陪同下首访非洲十国，这是我国第一代陪同周恩来访问非堪称联壁合领导人开拓对非工作的一次重大外交行动，访问取得了巨大成功，为中非友好奠定了坚实基础，树立了新中国与非洲交往史上的第一座丰碑。周恩来和陈毅两位领导人对贯彻我国的对外政策保持高度一致，共同为中国与非洲国家关系的五项原则以及我国对外援助八项原则倾注了大量心血。两人在具体的对外活动中总是高度默契合作，堪称珠联壁合的典范。周恩来视陈毅为知交、战友，十分尊重、赞赏；陈毅将周恩来奉为学习楷模、“外交老师”，对周恩来的外交思想和风格有着透彻的理解，并努力身体力行之，同时，陈毅身上又透露出独特的豪爽气质，其外交上的睿智、幽默、风趣经常博得人们的赞赏。在访问过程中，两人合作默契、并肩携手的生动事例不胜枚举。
两位领导人都热切期望与非洲民众广泛接触。周恩来和陈毅访问阿尔及利亚时，受到了阿人民的热烈欢迎，从机场至代表团下榻的国宾馆，20多公里长的道路两旁，30万群众夹道欢迎，建筑物上挂了周恩来和陈毅的巨幅照片，沿途楼房的各层阳台和窗口都挤满了欢迎的群众。周恩来和陈毅只能从轿车的窗口伸出头和手去向欢迎的人群握手致意。周恩来赞赏地说，进城才一年多的阿尔及利亚政府组织群众的能力这么强，这是了不起的。陈毅深有同感，以军人的口气笑着回答，在战争中锻炼出来的领导干部就是不一样噢。周恩来遗憾地说，阿国的群众那么热情，而我们只能坐在车内伸出头和手打打招呼，你看多么失礼啊!陈毅坦率地表达同样的看法，脱口道来：这样坐车面对群众挺别扭的，我看得改一改。原来，中方的安全部门考虑到刺杀戴高乐的法国地下军秘密组织在阿尔及利亚也有残余活动，所以不同意周恩来访问时坐敞篷汽车。后来，在周恩来和陈毅的共同要求下，中方安全部门才同意他们在对外活动时若遇群众夹道欢迎，可临时下车向群众招手致意。周恩来和陈毅为能同阿人民群众直接接触感到非常高兴和满意。
两位领导人在对外活动中风趣而充满睿智。在访问摩洛哥时。摩国王哈桑二世在举行盛大的国宴后，又让周恩来和陈毅留下品茶。其问，他问到了中国飞机、导弹生产情况以及固体燃料的前景等等，陈毅一一作了答复。紧接着，国王突然笑着说：“当今世界，像我们这样的国王、皇帝。已为数不多了，不知以后怎么办?”显然，国王在巧妙试探中方对国王抱何种态度。周恩来和陈毅听了，不约而同地哈哈大笑起来。周恩来自然地说：“你们可以组织一个委员会，开个会商量商量嘛!”陈毅进一步笑着说：“亚洲有个西哈努克亲王，我们是朋友，可邀请他参加开会。”周恩来又说：“陛下可以担任这个委员会的委员长嘛!”3人一起哈哈大笑起来。周恩来和陈毅就是这样地高度默契、融通一致，于谈笑间将国王对中国的不了解和疑虑自然地消融了。
两位领导人肝胆相照，以大无畏气概发展中非友谊。在访问几内亚时，几方向中方提出杜尔总统亲自陪同周恩来和陈毅到远离首都的金迪亚地区参观，中方只要带一名翻译，去时乘车，回来时坐直升飞机。中方打听到，直升飞机是苏联制造的，驾驶员来自捷克，加上几内亚国土大部分是高原和山地，在热带气候驾驶苏式直升机(为适应寒带飞行而设计制造的)具有一定危险性。因此，中方以安全为由，要求原车返回。但几方总统执意不变，认为这可减少坐长途车的疲劳。代表团把意见反映给陈毅，陈毅率直地说，此事由总理定，总理坐，我也坐。语气中充满着同周恩来患难与共、临危不惧的浩然大气。周恩来获悉后，明确地说：“人家总统、议长、国防部长。一、二、三号人物都能坐，我周恩来为什么不能坐?”外地参观结束后，杜尔与周恩来、陈毅及一名翻译同乘一架直升飞机返回首都。直到飞机安全降落了，大家心中的石头才落了地。
两位领导人在对外交往中谦和磊落，坚持顾全大局、求同存异。周恩来在访问突尼斯时，突总统布尔吉巴多次向中方表示异议，甚至发表批评意见，周恩来不但没生气，反而感谢说，这才是真正的朋友，有话直说，并且耐心地向对方解释疑虑。布尔吉巴被周恩来说服了，感动地说，我同意周恩来求同存异的方针，我们还要反帝反殖，突尼斯需要伟大的友谊，并一定要同中国建立外交关系。访问结束前，两国在《联合公报》中正式宣布中突建立外交关系。在摩洛哥国王举行的盛大宴会上，陈毅与国王的弟弟一位19岁的亲王同桌。这位亲王放言无忌，批评中国对外政策太强硬，称中国这么一个伟大国家不应如此，等等。陈毅听后不恼怒，反而表示欢迎年轻人的坦率，并耐心地向亲王解释中国的外交立场，对方的固执态度逐渐缓解。宴会结束时，亲王温和地说，元帅阁下，我很年轻，而你很有名望，经验很多，我讲的话请你不要见怪。他还坦诚地表示，当初我们能够复国独立，跟你们帮助越南人在奠边府打败了法国人有很大关系，所以要感谢你们。
周恩来访问非洲国家的日程很紧，领导人会谈、宴请、群众集会、记者招待会、重要参观等活动排得满满的。陈毅除参加有关重要活动外，还分担其它工作，其中重要一项就是陪同周恩来看望中国使馆工作人员后留下来做报告，传达中央方针政策，介绍国内外形势和出访情况等等。陈毅生动风趣的演讲，总是博得人们的阵阵掌声。在访问最后一站索马里时，陈毅用两个晚上向使馆同志作了7个小时的报告。他满怀喜悦地说，我们看到了一个觉醒的非洲。一个革命的非洲，一个前进的非洲。非洲人有自豪感，对自己命运有自信心，不像过去那样站不起来。他们产生了新的领袖和干部，产生了伟大的群众运动，不再跟着帝国主义和大国的指挥棒来考虑问题，而是根据自己整个大陆的翻身来考虑他们的建设，就像1949年解放了的中国一样，这是一种革命的苏醒，周恩来在索马里首都摩加迪沙群众集会上讲话中提出了“整个非洲大陆是一片大好的革命形势”的英明 论断，陈毅以生动的语言加以诠释，让使馆同志获益匪浅。代表团成员，负责起草重要文件和讲话稿的乔冠华兴致勃勃地听了报告，特别高兴地说，将陈毅副总理这两个晚上的讲话整理出来，这次出访总结的初稿就有了嘛!
第一次亚非会议的“万隆精神”对推动亚非国家民族独立运动产生了极大影响，经过一段时期的磋商、酝酿，亚非国家准备于1965年召开第二次亚非会议.非洲国家代表普遍希望会议地点能定在非洲。中国政府完全同意上述想法。1964年4月10日。代表们在印尼首都雅加达就第二次亚非会议召开事宜举行亚非国家外长会议，东道国点名邀请陈毅与会。陈毅抵达印尼后，努力了解会议动向，知悉当时多数国家认为第二次亚非会议应该在非洲国家召开，而东道国印尼总统苏加诺主张第二次亚非会议地点仍在印尼，时间放在1964年。为使会议顺利进行，陈毅积极做东道国的工作，迅速拜会苏加诺，进亍劝说：总统阁下如果主张第二次亚非会议在非洲开，就是支持了非州的斗争，顾全大局，表现了政治家的风度，证明你无私利打算，去发言就响亮。陈毅讲话立意新颖，寥寥数语，非常自然地打动了听者。苏加诺觉得很有道理，同意了在非洲召开，但仍主张1964年召开会议。接着，陈毅采取摆实示情况的做法，说服对方。他说：今年7月有阿拉伯首脑会议，8月卣非洲首脑会议，10月有不结盟国家会议，之后又有英联邦会议阳联合国大会，国家领导人长期生外开会怎么行呢?陈毅看出苏加诺的态度在发生变化，便进一步劝说，亚非会议和不结盟会议不应互相竞争，而应该互相补充，即使竞争也不必用抢先开会的办法陈毅循循善导的说理，终于让苏加诺松口道：时间问题还可以商量。
在会议地点、时间问题解决后.又出现了新的障碍。印度代表在会上突然提出邀请苏联参加第二次亚非会议。陈毅从容应对，采取了既坚持原则又注意灵活机动的斗争策略。他明确指出，苏联是一个传统的欧洲国家，这是小学生都知道的地理常识，苏联在联合国也从未参加亚非集团活动。中国反对邀请苏联，是为了维护万隆精神，维护亚非会议原则。如果屈从于某些大国的压力而放弃原则，将使我们亚非会议蒙受耻辱。陈毅的讲话句句有理，绝大多数国家代表都表示赞同。在这种有利的形势下，陈毅又做一些国家的工作，指出要从亚非团结的大局出发，主张作些让步，防止印度代表退出会议。最后，筹备会采纳了陈毅提出的方案，照顾了印度方面的面子，以未达成一致意见为由，“苏联与会问题”不列入首脑会议议程。大会秘书长、印尼副外长高兴地说，对陈毅元帅在本次会议中为维护万隆会议所做的贡献，对他民主地顾全大局的精神，我们要行脱帽礼表示感谢!
积极发展中非友好关系
周恩来对阿尔及利亚革命的胜利给予高度评价，称赞这是“继中国和古巴之后，60年代的伟大事件”。作为曾经统兵百万、横扫千军、战功卓著的元帅外交家，陈毅对以武装斗争夺取全国胜利的阿尔及利亚自然怀有特殊的好感。1958年12月，出任外长不久的陈毅热情地接待了阿尔及利亚临时政府向中国派遣的第一个正式代表团，并诚挚地向对方表示，“在今后的岁月里，阿尔及利亚人民永远可以指望六亿五千万中国人民对他们的坚决支持”。他同阿临时政府军备和供应部长谢里夫分别代表两国政府签署了联合公报，确定12月20日为两国建交日，中国成为除阿拉伯国家之外第一个承认阿临时政府的大国。阿方对中方的接待表示非常满意。赴机场欢送时，陈毅又向阿代表团表示：中国人民的心将永远同你们的心紧紧地连在一起。
陈毅四次涉足非洲，每次都访问阿尔及利亚，积极加强中阿友谊。最突出的是，1964年11月，陈毅率党政代表团访问阿尔及利亚，出席阿武装起义10周年庆典活动，与阿人民进行广泛接触。他向阿烈士墓敬献花圈，深切悼念为阿牺牲的革命烈士。陈毅同阿总统本?贝拉举行了两次会谈，双方就当时国际形势和中阿友好关系广泛地交换了意见。
几内亚于1959年10月4日同中国建立外交关系，是黑非洲地区最早与我国建交的国家。我国第一代领导人对中几友谊倾注了许多心血，陈毅也作出了宝贵的贡献。几内亚与中国建交不久就出现了“两个中国”的问题。当年，中国首批外交人员抵达几内亚首都科纳克里后，发现台湾当局的官员也在几首都，一个是台“部长”，另一个是台“外交部专员”。几内亚国家元首出面接见了台人员，甚至公开说，我们接见了来自福摩斯(即台湾)的中国代表团。还说，我们已经明确表示接受这个国家的外交机构。几方的做法显然有悖于中几两国建交公报精神，周恩来指示要审慎对待。我国驻几内亚大使馆作了交涉后，几方态度有些变化。对此，陈毅说了一句非常形象而幽默的话：人家人是黑的，心不一定是黑的嘛!还作出了重要批示：在反对“两个中国”的问题上，对美国和几内亚这样的非洲新独立国家还是应当区别对待。同前者针锋相对，对后者立场要明确，道理要讲清。只要几方承认中华人民共和国是中国人民的唯一合法政府，并保证今后不再发生同样的事件，交涉可以考虑适可而止。经中方向几方进一步做工作，阐明我国在原则问题上的鲜明立场，同时对几方的具体困难予以大力关心之后，几方的态度发生明显好转，表示同中国政府友好合作是他们的既定方针，今后不再发生此类事件，并明确表示要进一步加强双边关系。杜尔总统多次来中国驻几内亚大使馆做客。1960年9月10日，杜尔率领政府代表团访华，这是有史以来第一位非洲国家元首对中国的访问。9月12日晚上，毛泽东在中南海会见并宴请杜尔，刘少奇、周恩来、朱德、邓小平和陈毅等也陪同参加会见和宴会。
马里独立后，同中国友好，我国向马援建了一批与人民生活密切的轻工业和农业项目。周恩来非洲十国之行时，与马里总统凯塔多次进行深入会谈，我国对外援助八项原则首次写进两国联合公报。陈毅全过程地参加了这八项原则的制订，对八项原则的精神实质理解很深。他曾向国内同志意味深长地解释这些政策说：“帝国主义的援助，就是养成你对他的依赖。给你点鸦片烟抽，你抽上瘾就不能摆脱他了。中国的援助是别开生面。因为我们受过这种援助的害，就能体己谅人，帮助他们走上自力更生道路。
陈毅把加强中马友好合作关系作为对非工作的重点之一。1965年9月他访问了阿尔及利亚、马里、几内亚三国，其中对马里访问时间最长，达一个多星期。马里是有名的沙漠大火炉，热浪滚滚，成天让人感到在洗桑拿浴。陈毅不厩炎热天气，连续开展对外活动。不仅在首都，还到外地实地考察我国援建的项目。他同马里总统、部长、党的负责人多次进行会见、会谈，重点交换对发展经济的看法。 针对马里经济困难，陈毅向对方提出了按照自力更生方针加以解决的八项措施：(1)节约行政开支：(2)工业项目重新排队，尽量不搞非生产性建设；(3)节约外汇开支；(4)严惩贪污盗窃和投机倒把；(5)加强国防力量，封锁国境线，制止走私；(6)妥善安排支付外债和利息；(7)发展工农牧业生产：(8)中央指定得力干部管理经济。对于马里方面提出增加投资项目、扩大贸易额、帮助转口一部分马里需要外汇进口的物资和继续提供外汇贷款等要求，陈毅都表示予以积极考虑，答应我国可把罗马尼亚等国进口的石油转口给马里。马里政府对陈毅讲话非常满意，并根据讲话精神组成了贸易、交通运输等4个小组委员会，研究克服困难应采取的措施，在大抓农业生产、节约外汇开支等方面推出了一些新举措。讴歌非洲的压轴诗作
毛泽东十分赞赏陈毅的诗词，称他的诗词豪放奔腾，“有的地方像我”。周恩来非常推崇陈毅撰写的国际题材的诗词，曾将一些佳作介绍给外国领导人和朋友，藉以增进中外友谊。当年，陈毅陪同周恩来非洲十国之行，深知这是激发诗兴、抒写诗词的天赐良机，行前嘱其秘书准备了毛笔、墨盒和宣纸，还带了两本他最喜欢的书――李白和辛弃疾的诗词本。首次来到远隔重洋的非洲大地，陈毅触景生情，诗兴大发，挥洒自如，产生了多篇佳作，非洲之行也成为陈毅诗词撰写的黄金时期。《陈毅诗词选》中收录的国际题材方面诗词，将近一半来自此次非洲之行的吟唱。他以澎湃的激情，深邃的哲思，悠远的意境，恢宏的气势，洒脱的文字，对非洲古老的文明史、非州人民反帝反殖的英勇斗争、非州人民对中国人民的热情友好等方面，尽情地讴歌和诵唱。这些任作现已成为中国诗坛上歌颂非泖的压轴名篇，展示了陈毅这位诗人外交家的风采。
陈毅一踏上非洲大地，就作诗歌诵古奇迹金字塔，并将其与亚非拉人民的革命光辉联系起来，给人以莫大的信心和鼓舞力量。《赞金字塔》一诗大笔写道：“高塔巍巍数十寻，八百万方石砌成。艺术光垂数干载，雄哉伟哉古文明。”“金字塔，何巍巍！我叹往古智力之横绝，我歌现代革命之光辉。古既不能阻挡金字塔之建成，今休妄想阻挡革命的拉美和亚非。”诗句铿锵，古今相映，共铸辉煌，气魄浩大，激人奋进。
周恩来访非时，热情赞扬非洲一派大好的革命形势，称非洲是一个觉醒的大陆、战斗的大陆。陈毅以兴奋的心情，用诗笔描绘非洲。请看《非洲》一诗向我们展现的蓬勃朝气的新非洲景气：“非洲情况近如何?到处人民欢庆多。沙漠雪山初觉醒，重洋两海泛春波。殖民新旧谋转化，部族精华起沉疴。最喜斗争终获胜。不忘警惕荷干戈。”“黑非今日变红非，大地殖民已式微。象牙黄金还物主，白鹰翠乌有林归。衣冠似雪男雄壮，妙舞如花女褐菲。喜尔新来自豪惯，京垓兆亿庆春晖。”全诗让人赏心悦目，兴高彩烈，让读者切身体会到革命胜利后非洲人民的喜悦之情。
陈毅在访问西非国家时，目睹了残留在海滩边的无数个阴森森的关押奴隶的城堡，这是当年西方殖民主义者进行长达四个世纪的贩卖黑奴的铁证。陈毅向来嫉恶如仇，在这些惨绝人寰贩卖黑奴的历史遗址面前，心中涌出万丈怒火，真所谓“愤怒出诗人”。陈毅的一首《满江红?黄金海岸》雄词问世。且看神来之笔挥洒的全词：“尽是黄金，这海岸，摩天壁立。任掠夺，大洋风雨，神号鬼泣。贩卖黑奴过一亿，又教对岸红人绝。惊世间残暴竟如斯，两洲血。说宽恕，谁同意?论报应，亦不必。最无情只是斗争逻辑。独立非洲西北始，揭竿而起相踵接。看涤瑕荡垢土重光.全无敌。”这首词用字洗炼凝重，感染力强，震撼心魄，可谓博大精深、高亢激越的词中名篇。周恩来特别喜欢这首气魄宏大的佳作，尤其赞赏“两洲血”，认为其高度概括了当年殖民主义者迫害黑奴、残杀美洲土著居民的惨无人道的罪行。他曾热情地向一位亚洲国家领导人介绍这首词，并诠释词中“两洲血”的宏旨深义，希望亚洲人民要深切同情非洲人民遭受的大苦大难，进一步加强亚非团结的重要意义。
陈毅在访问苏丹时，被苏丹人民起义军当年浴血奋战赶走英国侵略者的斗争事迹深深感动，特别有感于英国殖民军头目戈登毙命于喀土穆。这个戈登，正是1860年参与指挥英法联军火烧圆明园，劫掠北京城，后又率领洋枪队镇压太平天国起义军的刽子手。他回英国后被派到苏丹任总督，继续作威作福，肆意欺压苏丹人民。1885年1月，苏丹人民揭竿而起攻入喀土穆，起义军在总督府门前用长矛刺穿了戈登的胸膛，为苏丹人民报了仇，也为中国人民讨还了血债。
向以热血刚肠著称的陈毅，自然对上述史事心花怒放，无比兴奋。在喀土穆登楼眺望皓月时。他追昔抚今，不胜欣喜和感慨.豪兴满怀，诗意油然升起，即以上述内容口占了一首诗，其中写道：“共和国宫楼上月，曾照戈登此驻节。将军东去肆劫掠，及返此间被击毙。人世沧桑每如此，岂有恶徒能不灭?不意成就中国苏丹之友谊，数十年来人艳说。”陈毅尽情地倾吐了对英雄的苏丹人民的敬仰之情，严厉鞭挞了殖民侵略者的暴行，深刻揭示了恶徒必毙的人世沧桑的正义之道。