Urząd burmistrza stolicy stanu Tennessee pełnił w latach 1991–1999.
Burmistrz Nashville Jako burmistrz Bredesen przykładał dużą wagę do spraw edukacji (m.in. zatrudnił 440 nowych nauczycieli, kazał wybudować 33 nowych szkół i odnowił 43 już istniejące).
W roku 1994 zdobył nominację demokratów na gubernatora Tennessee. Jego przeciwnikiem z ramienia republikanów był konserwatywny kongresmen Don Sundquist z 7. okręgu, który pokonał burmistrza niespodziewaną większością ponad 10% (był to zdecydowanie rok republikanów).
Przegrana nie zaszkodziła jednak ponownemu wyborowi Bredesena na burmistrza w 1995. Nie ubiegał się natomiast o trzecią kadencję w 1999.
Gubernator W roku 2002 gubernator Sundquist nie mógł ubiegać się o trzecią kadencję.
Bredesen ponownie ubiegał się o nominację i z łatwością uzyskał ją, pokonując republikańskiego kongresmena z dawnego okręgu Sundquista Vana Hilleary’ego. Jego kadencja zaczęła się dnia 18 stycznia 2003 roku.
Hilleary prowadził kampanię negatywną, starając się przedstawić Bredesena jako „liberała” i „znajdę z północy”. Mimo iż Tennessee leży na bardziej konserwatywnym południu, w większości jest stanem demokratycznym, choć partia ta utraciła większość wpływów w regionie na rzecz republikanów.