Aussi, lorsque le 21 juillet 1969, une partie du monde s'émerveille devant un homme plantant un drapeau sur la lune, l'Algérie regarde vers l'Afrique, le Festival panafricain qui a débuté ce jour-là étant le point d'orgue d'une décennie durant laquelle la capitale algérienne bouillonnante fut rebaptisée «la Mecque des révolutionnaires». Eldridge Cleaver, le ministre de l'Information du Parti des Panthères noires, affirma à Alger à un journaliste américain qui couvrait le festival : «Je ne vois pas quel bénéfice l'Humanité tirera de deux astronautes atterrissant sur la lune pendant que des gens sont assassinés au Vietnam et souffrent de faim même aux Etats-Unis.» Considéré comme fugitif dans son pays, il trouve refuge à Alger, qui lui accorde un soutien moral et matériel. «Le statut de fugitif de Cleaver n'était pas un handicap pour lui en Algérie. La plupart des officiels gouvernementaux avaient été qualifiés de criminels par les autorités françaises durant la guerre qui avait fait rage de 1954 à 1962. Ces hommes étaient conscients, concrètement, de la relation entre un mouvement révolutionnaire et le gouvernement établi, mais contesté, qui juge toutes les activités de soutien à la révolution comme criminelles. Des fugitifs de toute l'Afrique et d'autres parties du monde vivaient en paix à Alger, à mesure que la nouvelle nation devint l'hôte de représentants de presque tous les mouvements de libération d'Afrique, du mouvement de libération palestinien et de plusieurs groupes révolutionnaires extérieurs à l'Afrique, incluant des exilés politiques du Brésil et du Canada», explique Kathleen Neal Cleaver, chercheuse à l'université de Yale (à revérifier). Le BPP, qui avait découvert l'Algérie d'abord par les écrits de Franz Fanon, a trouvé ses plus forts soutiens parmi ceux qui subissaient directement la stratégie politique des États-Unis : les Palestiniens, les Vietnamiens, et les Nord-Coréens. Car parmi les mouvements présents à Alger ces années-là figurent notamment le Mouvement de l'indépendance de l'archipel des îles Canaries, le Front de libération du Québec, le Front de libération de la Bretagne, le Front de libération du Mozambique, le Front national de libération du Sud Vietnam, le ZAPU (Zimbabwe African People's Union), Le Front de l'unité nationale khmère (FUNK), l'ex-Front de libération du Dhofar, devenu Front populaire de libération d'Oman et du golfe Arabique, le Swapo (South-West African People's Organisation, Organisation du peuple du Sud-Ouest africain — qui deviendra la Namibie), le Parti africain de l'indépendance de la Guinée et du Cap-Vert (PAIGC), le Mouvement populaire pour la libération de l'Angola (MPLA), le Congrès national africain (ANC), d'Afrique du Sud et bien d'autres (l'on parle de 27 organisations au total). Les autorités algériennes établissent une hiérarchie des mouvements selon la justesse de leurs causes, accordant un statut diplomatiques à certaines d'entre elles (tel le Fatah palestinien, l'ANC sud-africain ou le gouvernement révolutionnaire provisoire du Vietnam du Sud (GRP)). Ceci ne manquera pas de quelques situations cocasses, comme la présence d'une ambassade parallèle du peuple noir, à l'heure où l'Algérie avait rompu ses relations diplomatiques avec les Etats-Unis suite à la guerre israélo-arabe de 1967, ou le cas particulier de l'ambassade du Cambodge : au moment de l'éviction de Norodom Sihanouk, en 1970, le gouvernement algérien n'ayant pas reconnu le gouvernement de Lon Nol, les représentants du Cambodge à Alger sont restés en place, mais au lieu du régime de Phnom Penh, ils continuent de représenter celui, en exil, de Sihanouk, et le FUNK. Il y avait sans doute une sincérité dans cet engagement auprès des peuples en lutte, après des années de guerre durant laquelle le FLN a bénéficie de peu de soutiens internationaux. L'Algérie avait à cœur d'être l'un des pays leaders des nations du Tiers-Monde. Mais la présence de ces militants turbulents finira par embarrasser le régime de Boumediène. Le détournement d'un avion américain, en août 1972, par un membre des Black Panthers, qui obtint une rançon record d'un demi-million de dollars signera le début de la fin. Refusant d'être considéré comme un receleur, le président Boumediene choisit de restituer l'argent à ceux auxquels il avait été extorqué, précipitant ainsi le départ des Cleavers et de leurs camarades. Ce divorce, jumelé à l'acquisition de nombreux mouvements africains de leur indépendance, marquera un tournant dans l'activisme politique algérien. Renouant les liens avec les états-Unis grâce à l'entremise d'Henry Kissinger, c'est sur la scène diplomatique que le pouvoir algérien défendra un nouvel ordre économique mondial. Ayant lancé des projets industriels et nationalisé ses hydrocarbures, l'Algérie devait aussi s'adapter aux réalités de la politique étrangère, réfléchir à consolider et diversifier ses partenaires économiques. A l'ONU, la diplomatie algérienne réussit à mettre la cause palestinienne et la lutte anti-apartheid au devant de la scène. A partir de ces années-là, une nouvelle ère commence, ce sera l'âge d'or de la diplomatie algérienne.
