Kariera polityczna przed wyborem na gubernatora Pierwszy raz o stanowisko publiczne ubiegał się w roku 1987, kiedy zgłosił swoją kandydaturę na burmistrza Nashville z ramienia demokratów. W czasie prawyborów zdobył drugiej miejsce za kongresmenem Billem Bonerem z 5. okręgu wyborczego. Jednakże 42% głosów, jakie zebrał Boner, dawały mu prawo do drugiej tury. Bredesen przegrał jednak ponownie z Bonerem, który wykorzystywał w kampanii jego pochodzenie z północy (Tennessee leży bowiem na południu). Boner wygrał wybory i przez cztery lata (1987–1991) pełnił urząd burmistrza stolicy Tennessee.
Rok później (1988) Bredesen ponownie ubiegał się o wybieralne stanowisko, tym razem na szczeblu federalnym (miejsce w Kongresie, opuszczone przez Bonera), ale i tu znalazł się na drugim miejscu, gdyż zwycięzcą został syn byłego gubernatora Franka D. Clementa Bob Clement, który z łatwością wygrał właściwe wybory (okręg ten od roku 1875 nieprzerwanie znajduje się w rękach demokratów).
Mimo dwukrotnych porażek, Bredesen wyrobił sobie dzięki udziałom w tych kampaniach nazwisko i pewne poparcie, co widoczne było w roku 1991, kiedy ponownie kandydował na burmistrza i wygrał dużą większością głosów.