Od 1934 roku działał w sprzeciwiającym się nazizmowi ruchu Bekenennde Kirche.
W 1945 roku aktywnie uczestniczył w tworzeniu struktur CDU, zarówno w Essen, jak i w całej Nadrenii. Jesienią 1946 został burmistrzem zniszczonego rodzinnego miasta. W 1947 roku w pierwszych powojennych wyborach do landtagu Nadrenii Północnej-Westfalii uzyskał mandat deputowanego z list CDU i został członkiem rządu landowego pod kierownictwem Karla Arnolda, obejmując tekę ministra sprawiedliwości, pełniąc tę funkcję do 1948 r.
W wyborach parlamentarnych w 1949 roku z list CDU został wybrany do Bundestagu. W latach 1949–1950 był ministrem spraw wewnętrznych w I rządzie kanclerza Konrada Adenauera. Jednak różnica w poglądach na temat remilitaryzacji państwa, której był przeciwnikiem, doprowadziła do odejścia Heinemanna z gabinetu Adenauera.
W listopadzie 1952 roku Heinemann wraz z założył Gesamtdeutsche Volkspartei (GVP), która w wyborach parlamentarnych w 1953 roku nie dostała się do Bundestagu. W 1957 roku wstąpił do SPD, z której list uzyskał mandat do Bundestagu. W okresie Wielkiej Koalicji (CDU/CSU – SPD, 1966–1969) pełnił urząd ministra sprawiedliwości. Zasłynął wtedy wyrażeniem zrozumienia dla rozruchów studenckich w 1968 roku.