Elle adhère au SPD à l'âge de 23 ans, et devient en 1974 présidente fédérale des Jeunes socialistes (Jusos), où elle acquiert son surnom de «Heidi la rouge». En 1979, elle est élue députée européenne, un mandat qu'elle exerce jusqu'à son élection au Bundestag, en 1987. Six ans plus tard, elle se présente à l'élection du président du SPD, qui se tient pour la première fois au suffrage direct, mais termine troisième avec 27% des voix. Devenue vice-présidente fédérale du parti, elle est nommée ministre fédérale de la Coopération économique en 1998 dans la coalition rouge-verte de Gerhard Schröder, étant reconduite en 2005 dans la grande coalition d'Angela Merkel. Elle quitte ce poste en 2009 après onze années de mandat, établissant ainsi un record de longévité, et continue de siéger comme députée fédérale.
Par ailleurs, elle préside pendant deux ans à partir de 1977 le Bureau européen de coordination internationale de la jeunesse.
Nom de famille
Née Heidemarie Zeul, elle épouse en 1965 Norbert Wieczorek, membre du SPD et futur député fédéral. Malgré le fait qu'ils aient divorcé au bout de quatorze ans, elle a toujours conservé le nom de famille de son époux accolé au sien.
Neuf ans plus tard, en 1974, elle est élue présidente fédérale des Jusos, mouvement de jeunes du SPD, et le reste pendant trois ans. À ce poste, elle a acquis son surnom de «Heidi la rouge» (Rote Heidi), aussi bien en référence à la couleur de ses cheveux qu'à ses opinions politiques, très marquées à gauche.
Présidente des sociaux-démocrates de Hesse du sud entre 1988 et 1999, elle se présente à la présidence fédérale en 1993 au cours de la première et unique primaire au scrutin direct dans l'histoire du parti, mais est finalement battue par Rudolf Scharping, qui obtient 40% des voix, et Gerhard Schröder avec 33%, alors qu'elle récolte les 27% restants. Elle est alors élue vice-présidente fédérale.
En , elle soutient l'élection d'Andrea Nahles, issue de l'aile gauche du parti, comme secrétaire générale fédérale contre Karl-Josef Wasserhövel, le candidat choisi par le président Franz Müntefering, classé plus à droite. L'élection de Nahles par le comité directeur fédéral conduit Müntefering à renoncer à la direction du parti. Face aux fortes critiques dont elle fait l'objet dans l'appareil, elle décide de renoncer à sa vice-présidence fédérale lors du congrès convoqué peu après et qui voit l'élection de Matthias Platzeck à la présidence du SPD.
En 1979, elle est élue députée au Parlement européen et siège à la commission du commerce extérieur. Réélue en 1984, elle est contrainte de démissionner trois ans plus tard, à la suite de son élection comme députée fédérale au Bundestag le .