Après la chute du mur de Berlin, on observe progressivement le redéploiement13 des amicales en Allemagne et les tentatives de création d'amicales dans les pays d'Europe orientale; ces dernières ne sont pas toujours couronnées de succès il est vrai. En effet, certains pays interdisent à leurs ressortissants de servir dans des armées étrangères et lorsque des anciens légionnaires rentrent dans leur pays natal, ils doivent souvent affronter des procédures à leur encontre, voire des condamnations.(14)

Le général Jean-Claude Coullon lui succède le 11 mai 1991, et est confirmé dans ses fonctions par l'assemblée générale du 17 novembre. En 1995 le congrès de Fréjus correspond aussi à l'inauguration du mémorial de Fréjus dédiés aux combattants d'Indochine. A cette occasion le président prononce une allocution dans laquelle il appelle de ses vœux une cérémonie annuelle du souvenir dédiés aux combattants d'Indochine.

Les faits marquant de la présidence du général Coullon sont::

- En 1996 la création d'un «Comité de la Mémoire» qui sera placé sous la direction du général (c.r.) Colcomb

- De 1997 à 1999 la fédération lance l'idée de faire bénéficier tout légionnaire étranger blessé en service commandé de la nationalité française. Cette action provoque un débat national sur le sujet et abouti à l'adoption en décembre 1999 du texte de loi «Français par le sang versé»(15)

- En 2000 le lancement de la demande du droit d'ester en justice pour la fédération à l'encontre de personne ou organisme attaquant les anciens de la Légion étrangère (au même titre que la LICRA peut le faire à l'encontre de tout individu ou organisme manifestant des propos raciste). Cette demande n'a pas encore abouti mais la fédération persévère dans son action.

- L'année 2001 est aussi marquée, dans le domaine de la communication, par l'ouverture du site internet de la fédération, dont nous verrons plus loin le détail.

Le 1/7/2001, le général Coullon fait élire le général Rideau à sa succession à la tête de la fédération. L'année marque aussi l'ouverture du site internet de la fédération dont nous reparlerons plus loin.