Des Jeux Méditerranéens 1963 aux JO 1964
Militaire de carrière, Gammoudi s'est d'abord spécialisé dans le cross-country. Rapidement, couvé par son commandant et entraîneur Hassine Mamouda, il décide de s'aligner sur le 5 000 mètres. Il capte pour la première fois l'attention internationale à l'occasion des Jeux Méditerranéens 1963, organisés à Naples, où il remporte les 5 000 et 10 000 mètres.
Victime d'une tendinite chronique, il reste virtuellement inconnu lorsqu'il arrive aux Jeux olympiques d'été de 1964 tenus à Tokyo. Le favori est alors le recordman en titre, l'Australien Ron Clarke, qui impose un tempo rapide durant toute la course. Lors du dernier tour, ce dernier est parvenu à éloigner tous ses rivaux principaux à l'exception de Gammoudi et de l'Américain Billy Mills. Durant la toute dernière partie de la course, Clarke et Gammoudi se succédent en tête ; sur les 50 derniers mètres, Gammoudi mène la course avant d'être finalement dépassé par Mills qui remporte la médaille d'or. Gammoudi remporte alors la première médaille d'argent de l'histoire du sport tunisien.
Deux jours plus tard, Gammoudi est qualifié pour le 5 000 mètres mais, pour des raisons qui restent inexpliquées, se retire de la finale.
Des Jeux Méditerranéens 1967 aux JO 1968
Gammoudi défend avec succès ses titres aux 5 000 et 10 000 mètres durant les Jeux Méditerranéens 1967 organisés à Tunis et se place alors comme l'un des favoris pour les Jeux olympiques d'été de 1968 à Mexico. Dans la finale du 10 000 mètres tenue le 17 octobre, Gammoudi est en tête durant la majorité de la course. Lors du dernier tour, la tête se réduit à trois coureurs : Gammoudi, le kényan Naftali Temu et l'Éthiopien Mamo Wolde. Ce dernier sprinte durant les derniers mètres et dépasse Gammoudi, lui laissant finalement la médaille de bronze. Deux jours plus tard, Gammoudi se qualifie pour la finale du 5 000 mètres où trois coureurs se retrouvent en tête durant le dernier tour : Gammoudi devançant Temu et un autre Kényan, Kip Keino. Sur un rythme très rapide, et malgré la charge des deux Kényans, Gammoudi remporte finalement la médaille d'or en 14’05’’. Célébré à son retour à Tunis, il est aussitôt élevé du grade de sergent à celui de lieutenant par le président Habib Bourguiba.
Des Jeux Méditerranéens 1971 à la retraite
Aux Jeux Méditerranéens suivants, organisés à İzmir en 1971, Gammoudi remporte la médaille d'argent aux 5 000 mètres. Malgré cette moins bonne performance, il reste l'un des favoris pour les 5 000 et 10 000 mètres aux Jeux olympiques d'été de 1972 à Munich. Dans la finale du 10 000 mètres, un groupe compact de neuf coureurs mènent la course à un rythme soutenu lorsque, au niveau des 4 800 mètres, le Finnois Lasse Virén tombe, causant également la chute de Gammoudi à sa suite. Virén se relève vite et remporte tout de même la course alors que Gammoudi prend plus de temps pour repartir et, après avoir rattrapé son retard de 100 mètres après un tour et demi, abandonne finalement.
Contrairement aux 10 000 mètres, les premiers tours du 5 000 mètres sont courus à un rythme lent avec la présence de Gammoudi dans un groupe compact durant 3 000 mètres. C'est durant les derniers 2 000 mètres que la course s'accélère, avec le détachement de Virén et du champion américain Steve Prefontaine. Les derniers mètres tournent au sprint avec Virén battant finalement Gammoudi d'à peu près dix mètres au cours de ce qui constitue la dernière compétition majeure de ce dernier. En effet, Gammoudi est privé d'une quatrième participation d'affilée en raison du boycottage des Jeux olympiques d'été de 1976 par les pays africains voulant protester contre la présence des sportifs sud-africains.
Il n'abandonne toutefois pas le monde du sport de haut niveau puisqu'il est appelé, dès la fin de sa carrière, à exercer de hautes responsabilités au sein de la Fédération tunisienne d'athlétisme.