So war es nur konsequent, wenn Heinemann schon 1967 als Justizminister in der Großen Koalition einen Gesetzentwurf vorlegte, der vorsah, die Verjährungsfrist für Nazimordtaten, die 1969 ablief, aufzuheben. Gerade die Älteren, so fand er, sollten sich endlich der Vergangenheit stellen, statt die Erinnerung daran zu verdrängen oder jede Mitverantwortung zu leugnen. Als Bundespräsident sah Heinemann es als seine vordringliche Aufgabe an, die von Deutschland überfallenen Nachbarländer wie Holland, Dänemark und Norwegen zu besuchen und dort der von der deutschen Besatzung oder Polizei ermordeten oder verschleppten Menschen zu gedenken.

Den Krieg hatte die Familie Heinemann heil überstanden. Es war unvermeidlich, dass die britische Besatzungsmacht, auf der Suche nach Deutschen mit blütenweißer Wesche, auch Heinemann ein Amt antragen wollte. Nach anfänglichem Sträuben wurde ihm klar, dass einer wie er sich nun in der Politik zu bewähren hatte. Heinemann wurde zum Mitbegründer der Christlich Demokratischen Union in Essen

im Jahre 1946 wurde er von der Bevölkerung mit großer Mehrheit zum Oberbürgermeister der Stadt gewählt. In seiner Antrittsrede versäumte er nicht, seinem von den Engländern eingesetzten Vorgänger, dem Kommunisten Heinz Renner, zu danken, weil er sein Amt "mutvoll und tatkräftig verwaltet" habe. Für Heinemann verstand es sich von selbst, dass er 1964 mit seiner Frau bei der Trauerfeier für den nach langem Siechtum gestorbenen ehemaligen Bundestagsabgeordneten erschien, mochten seine politischen Gegner diese Geste auch noch so missverstehen. Nie kannte Heinemann Berührungsangst vor Politikern mit anderer Meinung.

Konrad Adenauer hatte mehrmals vergeblich versucht, Heinemann als Mitglied des Parlamentarischen Rates, wo der Jurist gewiss gute Arbeit hätte leisten können, oder als Kandidaten für den Bundestag zu gewinnen, denn er wusste, welches Ansehen der Präses der EKD-Synode unter den Protestanten in der Union genoss. Als sich jedoch im Herbst 1949 herausstellte, dass unter den 13 Ministern der CDU/CSU in der ersten Bundesregierung nur einer ein Protestant war - der Wirtschaftswunderminister Ludwig Erhard -, da sah sich Adenauer genötigt, Heinemann das Amt des Bundesinnenministers anzutragen. Besonders der linke Flügel, der sich an das sozialorientierte Ahlener Programm gebunden fühlte, bestand auf der Berufung.

Heinemann ist der Wechsel nach Bonn schwer gefallen. Er ging erst, nachdem ihm die Rheinstahl AG zugesichert hatte, er könne später in den Vorstand zurückkehren. Da Heinemann die autoritären Anwandlungen des Kanzlers nicht hinnehmen wollte, war das Ende seiner Kabinettsmitgliedschaft abzusehen. Ende August 1950 kam es zum Eklat: Der Kanzler hatte hinter dem Rücken des Kabinetts den Amerikanern 150 000 deutsche Soldaten zur Verteidigung Europas angeboten. Die Minister erfuhren es aus der Presse. Heinemann, der als Sicherheitsminister zumindest hätte gefragt werden müssen, protestierte: "Das mache ich nicht mit!" - Adenauer: "Was bedeutet das, Heinemann?" - "Ich scheide aus!"

Der Rücktritt verzögerte sich noch bis zum 10. Oktober, weil Adenauer und die Partei einen Kompromiss anstrebten. Heinemann blieb hart. Er hielt es für unerhört, wolle Deutschland nach zwei verlorenen Weltkriegen sich noch einmal bewaffnen - diesmal mit dem Risiko, darüber die Wiedervereinigung des geteilten Deutschlands für lange Zeit zu verspielen.

Nun wurde es auf einmal sehr einsam um Heinemann. Die CDU kehrte sich von ihm ab, und der Aufsichtsrat der Rheinstahl AG wollte den Dissidenten nicht wieder aufnehmen. Man einigte sich auf eine Pension, von der sich leben ließ.