Wkrótce zaangażował się w działalność polityczną, politykę, wstępując w 1980 do nowo utworzonego ugrupowania Zielonych. W 1983 z ramienia tej partii został wybrany na deputowanego do Bundestagu. W parlamencie zasiadał do 1986 i ponownie w latach 1987–1989, będąc jednym z rzeczników frakcji swojej partii. W 1989 zrezygnował z mandatu deputowanego, przechodząc do Socjaldemokratycznej Partii Niemiec. Do niższej izby niemieckiego parlamentu powrócił z ramienia SPD w 1990. Z powodzeniem ubiegał się o reelekcję w wyborach w 1994, 1998, 2002 i 2005, wykonując mandat poselski do 2009, gdy zdecydował się zakończyć swoją parlamentarną działalność. W ramach SPD zajmował się początkowo głównie problematyką dawnych landów wschodnich.
W październiku 1998, po zwycięskich wyborach parlamentarnych, znalazł się w rządzieGerharda Schrödera jako minister spraw wewnętrznych. Stanowisko to zachował również po wyborach w 2002 w drugim gabinecie dotychczasowego kanclerza. Urząd ten sprawował do listopada 2005.
