Fils d'un chef de gare[1], il entre en 1902 aux PTT, comme surnuméraire puis commis. À la suite de sa participation le , il est déplacé de Paris à Avignon. Il reste neuf ans dans le Vaucluse, où il devient un des dirigeants de la Fédération socialiste; il est candidat député en 1910 et 1914. En 1915 il est de retour à Paris. Il est un des fondateurs du Parti communiste français, en 1920, lors du congrès de Tours.
En 1921 il entre au comité directeur de ce parti. Cet organisme prend le nom de comité central en 1924. Henri Gourdeaux en sera membre, jusqu'en 1947. En 1924, il est emprisonné trois mois pour « attentat contre la sureté extérieure et intérieure de l’État », après avoir dénoncé l'occupation de la Ruhr ordonnée par le gouvernement de Raymond Poincaré afin de contraindre l’Allemagne à accélérer les paiements[2].
En 1925, il est élu secrétaire général de la fédération des PTT de la CGTU, fonction qu'il détient jusqu'à la réunification syndicale de 1936. Antoinette Gilles le tient informé des mouvements de la CGT[3].
Membre du bureau confédéral de la CGTU en 1933, il est élu en 1936 secrétaire-adjoint de la fédération postale CGT réunifiée, dont Albert Perrot est le secrétaire général. Il n'est pas réélu à ce poste en 1938.
De 1940 à 1944, il est l'un des dirigeants clandestins du syndicalisme postier, en même temps qu'il occupe des responsabilités dans le PCF. Il avait, à ce titre, été condamné à mort par contumace
1945 : élu au conseil municipal de Paris, Henri Gourdeaux siège à nouveau au conseil général de la Seine, jusqu'en 1959. Il fait partie du groupe communiste de cette assemblée.