Engagé au sein du parti Venstre, il est élu conseiller municipal d'Aalborg lors des élections locales de [2]. Après sa réélection pour un second mandat en , il devient conseiller municipal exécutif chargé de la santé et de la culture le [3],[4].
En , il annonce son intention de briguer l'investiture de son parti comme tête de liste aux élections régionales de dans la région du Jutland du Nord[5]. En , il remporte le vote interne des militants en battant Lone Sondrup, première vice-présidente du conseil régional[6]. Lors de l’élection du , sa liste remporte 25,2% des voix, en deuxième position derrière celle de la présidente sociale-démocrate sortante Ulla Astman, qui en recueille 35%[7]. Toutefois, les partis de droite remportent 21 sièges au conseil régional, contre 20 pour les partis de gauche, permettant à Mads Duedahl de devenir président du conseil régional avec le soutien du Parti populaire conservateur, de La Nouvelle Droite et du Parti populaire danois[8]. Ulla Astman occupait le poste depuis la création de la région le , faisant de Duedahl la première personnalité de droite à remporter la présidence[9].
En , quand la présidente de la région Danemark du Sud, Stephanie Lose, est nommée au gouvernement, il lui succède comme vice-président de Dansk Regioner (l'association des régions danoises)[10].
Candidat à un second mandat lors des élections régionales de 2025, sa liste arrive en tête avec 27% des suffrages. Il forme ensuite une coalition avec l'ensemble des partis représetés au conseil régional, à l'exception de la Social-démocratie, pour être reconduit pour un second mandat à la présidence[11]. Après le scrutin, il est également choisi pour prendre la présidence de Danske Regioner, l'association représentative des régions danoises[12].
