W 1980 założyła fundację Salt Lake Education Foundation i była jej dyrektorem przez 9 lat.
Była reprezentantką w stanowym parlamencie od 1981 do 1989.
W latach 1989–1992 pełniła funkcję dyrektora Wydziału Rozwoju Społeczności Utah.
Od 1993 do 2003 pełniła funkcję zastępcy gubernatora Utah. Była pierwszą kobietą, która pełniła tę funkcję. W czasie swojej kadencji kierowała wieloma inicjatywami, takimi jak programy edukacyjne i programy rozwoju siły roboczej. Kierowała Grupą Zadaniową ds. Reformy Opieki Zdrowotnej, która ustanowiła Program Ubezpieczeń Zdrowotnych dla Dzieci, zapewniający tanią opiekę zdrowotną dzieciom z Utah. Walker zwołała także Komitet Koordynacyjny ds. Bezdomnych w Utah, którego celem było położenie kresu bezdomności chronicznemj poprzez tworzenie tanich mieszkań i usług wsparcia.
Po tym jak w 2003 gubernator Mike Leavitt zrezygnował z urzędu, aby zostać administratorem Environmental Protection Agency, 5 listopada Walker przejęła jego funkcję na drodze sukcesji i została pierwszą kobietą na tym stanowisku. Pełniąc urząd nie zawsze zgadzała się ze swoją partią w kluczowych sprawach. Na przykład zawetowała ustawę o kuponach do szkół publicznych, tłumacząc, że jej zdaniem zmniejszyłoby to budżet stanu przeznaczony na finansowani szkół.