Professeur, Henri Stoll est membre des Verts depuis 1989. C'est cette année-là qu'il décroche son premier mandat politique en tant que conseiller municipal d'opposition à Kaysersberg, dont il sera élu maire en 1995 et réélu par la suite (2001, 2008). Il devient 1er vice-président de la communauté de communes de la vallée de Kaysersberg et est conseiller général du Haut-Rhin depuis 2004.
En , il annonce sa candidature à l'élection primaire d'Europe Écologie Les Verts, qui doit désigner le candidat de ce parti à l'élection présidentielle. Il précise : « Je représente la base des écolos, les gens simples, dont une partie ne se retrouve pas dans les images de l'écologie spectacle »[1]. À l'issue du premier tour, il termine troisième avec 5,02 %[2].
Henri Stoll est appelé à comparaître le à la suite d'une plainte déposée par le conseiller général de Saint-AmarinJean-Jacques Weber, pour avoir déclaré à deux reprises que son élection était « à vomir », en faisant référence à ses ennuis judiciaires du passé[3].
Candidat dans la deuxième circonscription du Haut-Rhin lors des élections législatives de 2012, il est soutenu dès le premier tour par EELV, le PS et le MEI. Avec 21,15 %, il est largement distancé au premier tour par l'UMP Jean-Louis Christ (45,92 %) mais accède au second tour[4].