Münsteren, Münchenben, Göttingenben, Marburgban és Berlinben tanult közgazdaságtant, politikatudományt és jogtudományokat. Államtudományi és jogtudományi doktorátust szerzett. Már diákként aktívan tevékenykedett a Német Demokrata Párt (Deutsche Demokratische Partei) diákszekcióiban. 1928-ban jogtanácsosként helyezkedett el Essenben, a Rheinische Stahlwerke acélgyárban. 1933-tól a Kölni Egyetemen tanított gazdasági és bányajogot. 1934-ben csatlakozott a Hitvalló egyházhoz, amely elutasította a nemzetiszocialisták hatalomra törését. A Németországi evangélikus egyház tanácsának tagja, az Össznémet szinódus elnöke valamint 1936 és 1952 között az YMCA elnöke volt Essenben.
1945 októberében a Német evangélikus egyház elnökségi tagjaival együtt aláírta a stuttgarti bűnvalló nyilatkozatot. 1946-ban részt vett a Kereszténydemokrata Unió alapításában. A brit megszálló katonai kormány Essen tiszteletbeli polgármesterévé nevezte ki, majd 1946-ban főpolgármesterré választották. A tisztséget 1949-ig töltötte be.
1946-ban a Kereszténydemokrata Unió képviselője Észak-Rajna-Vesztfália tartományi gyűlésében. 1947/48-ban a tartományi kormányban igazságügyi miniszter. 1948 és 1961 között a Világegyházak Tanácsában a nemzetközi ügyekkel foglalkozó bizottság tagja volt. 1949-ben a belügyminiszteri tárcát kapta meg Konrad Adenauer első kormányában, de egy év után lemondott, mert Adenauer a minisztériumot megkerülve ajánlott fel német kontingenst az európai hadsereg számára. 1951-ben közösségbe hívta mindazokat, akik ellenezték Németország újrafelfegyverzését, mert veszélyeztette a két német állam újraegyesítését.
1952-ben kilépett a Kereszténydemokrata Unióból és új pártot alapított, az Össznémet Néppártot (Gesamtdeutsche Volkspartei), ami 1957-ben megszűnt. Ezt követően Németország Szociáldemokrata Pártjának lett a tagja, és újra képviselő a Bundestagban. 1958. január 23-án heves parlamenti vitában Adenauer szemére vetette, hogy rossz külpolitikát folytat, amellyel veszélyezteti a német újraegyesítést. Adam Rapacki, lengyel külügyminiszter javasolta az ENSZ közgyűlésén, hogy Lengyelországot, Nyugat- és Kelet-Németországot atommentes övezetté nyilvánítsák. Heinemann a javaslatban a kelet–nyugati párbeszéd elindításának lehetőségét látta. 1961-ben, közvetlenül a berlini fal felépítése után úgy nyilatkozott, hogy a Brandenburgi kapunál Adenaeur megkapta a választ Németország-politikájára. 1964-ben Moszkvába látogatott Eugen Kogon történésszel.
1966-ban igazságügyi miniszterré nevezték ki Willy Brandt ajánlására Kurt Georg Kiesinger kormányában. Jelentős büntetőjogi reformot sikerült véghezvinnie. Kiállt a gyilkosság, és különösen a náci büntettek elévülési idejének eltörléséért. 1969. március 5-én Németország elnökévé választották. Külföldön pozitívan fogadták Heinemann személyét. Támogatta Willy Brandt új keleti politikáját. Egyik legfontosabb feladatának tartotta, hogy honfitársait polgári viselkedésre és cselekvésre tanítsa, hogy aktívan támogassák a demokráciát, a jogállamiságot és a társadalmi igazságosságot. Nem államelnöknek, hanem az állampolgárok elnökének nevezte magát. Az újévi fogadásokra egyszerű embereket is meghívott, és ez hagyománnyá vált. Fontos volt számára, hogy Németország kibéküljön szomszédaival, és hogy a békét megőrizzék Európában. Visszavonulása után újra Essenben élt, és aktívan követte a politikai eseményeket.