Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section «Notes et références».
Avocat à Salt Lake City, Anderson se présente à la Chambre des représentants en 1996, mais il est battu par son rival républicain Merrill Cook. Ayant cependant reçu une majorité de 55% des voix dans la ville de Salt Lake City, il prépare alors activement sa campagne pour les élections municipales.
Maire de Salt Lake City
Anderson est élu maire de Salt Lake City en 1999. Ce démocrate de gauche se retrouve à la tête d'une ville plutôt conservatrice, où il mène une politique progressiste et écologiste en soutenant le droit des homosexuels et se prononce ouvertement pour le mariage entre personnes de même sexe et contre la guerre en Irak. Écologiste convaincu, il entreprend de remplacer les véhicules du parc de la ville par des véhicules propres afin de pouvoir tenir la promesse de respecter le protocole de Kyoto. Militant anti-tabac, il dénonce les lois anti-alcool de l'État et s'oppose à la reconnaissance de l'anglais comme langue officielle de l'Utah. Il est réélu en 2003.
Fragilisé par l'écrasante victoire de George W. Bush dans l'Utah (72%) et par son bon score à Salt Lake City en , il n'en abandonne pas pour autant sa rhétorique progressiste et anti-guerre. En , à l'occasion d'une visite du président Bush à Salt Lake City pour défendre l’intervention en Irak, Anderson envoie des courriers électroniques pour mobiliser les militants anti-guerre de la ville, où deux mille personnes répondent à son appel.
En , Anderson accorde aux partenaires non mariés des employés municipaux, qu’il s’agisse de couples hétérosexuels ou homosexuels, les mêmes droits qu’aux couples mariés alors qu'en , 66% des votants de l'Utah rejetaient par référendum toute possibilité de mariage homosexuel ou d'union civile. Le score se montait à 82% hors Salt Lake City, alors que 54% des habitants de la ville au contraire l'approuvaient.
Controverses
Anderson est à l'occasion brocardé pour son franc-parler, sa mégalomanie et son ignorance des lois de l'Utah. Ainsi, à l’occasion d'un festival international de jazz à Salt Lake City, il paie sur le budget de la municipalité une addition de 634 dollars correspondant à une partie du diner et de la consommation en bières de ses convives alors que les règlements de la ville interdisent aux représentants municipaux de payer des boissons alcoolisées avec des fonds publics. C'est à cette occasion qu'il déclenche un scandale en comparant la vie dans l'Utah à un roman de Kafka où on aurait introduit quelques talibans. Il fait alors supprimer les règlements qui l'avaient pris en faute (dont on trouve également l'équivalent à Las Vegas).
Depuis son accession à la mairie, plus de 41 employés de la haute administration municipale ont été poussés à la démission, officiellement pour incompétence représentant une rotation de l'emploi exceptionnellement haute de 240%. Anderson est accusé à maintes occasions d'utiliser un langage ordurier, d'organiser une ambiance de travail détestable et de ridiculiser en privé les principes de l'Église de Jésus-Christ des saints des derniers jours[réf.nécessaire].
En , Anderson est encore accusé d'avoir utilisé des fonds municipaux lors de son voyage en Italie en vue des Jeux olympiques de Turin en 2006.
