Mit Beginn der nationalsozialistischen Diktatur verlor er seine Anstellung und seine Ämter. Außerdem wurde er für drei Tage in „Schutzhaft“ genommen. Trotz dieser negativen Erfahrung schreckte er nicht davor zurück, sich weiterhin politisch zu engagieren – nun jedoch illegal. So verteilte Steinhoff heimlich sozialdemokratische Flugschriften. Bereits 1934 wurde er wegen derartigen Aktionen wegen Hochverrats angeklagt, jedoch aus Mangel an Beweisen wieder aus der Untersuchungshaft entlassen. Steinhoffs Wagemut überrascht noch mehr, wenn man bedenkt, dass er mittlerweile verheiratet war. Um Geld zu verdienen, arbeitete er als Handelsvertreter und eröffnete 1937 ein Herd- und Ofenreinigungsgeschäft. Ein Jahr später wurde er jedoch von der Gestapo verhaftet und in der berüchtigten Dortmunder Steinwache schwer misshandelt. Erneut wurde er wegen Hochverrats angeklagt, und diesmal zu drei Jahren Zuchthaus verurteilt. Aus der Deutschen Arbeitsfront (DAF), der er seit 1933 angehörte, wurde er ausgeschlossen. 1941, nach dem Ende seiner Haft, fand er eine Stelle als Metallarbeiter bei einer Firma in Iserlohn. Nach dem gescheiterten Hitlerattentat im Juli 1944 wurde Steinhoff allerdings wieder verhaftet und in das KZ Sachsenhausen verfrachtet. Hier begegnete er erneut Fritz Henßler, den man ebenfalls im Konzentrationslager gefangen hielt. Steinhoff kam erst mit Kriegsende wieder in Freiheit. Die Gefangenschaft hatte ihm stark zugesetzt, u.a. litt er seitdem an einem chronischen Magenleiden.4 Umso erstaunlicher ist, dass Steinhoff die Erlebnisse der KZ-Zeit folgendermaßen zusammenfasste: „Mir ist es soweit ganz gut ergangen, aber was um einen vor sich ging, das war so schrecklich, daß es diejenigen, die es nicht gesehen hatten, nicht glauben konnten.“5
Nach dem Zweiten Weltkrieg war Steinhoff unmittelbar beim Wiederaufbau der SPD beteiligt. So wurde er stellvertretender Vorsitzender des SPD-Bezirks Westliches-Westfalen und 1950 Mitglied des Parteivorstandes. Bereits Anfang des Jahres 1946 wurde Steinhoff, der fest in der Kommunalpolitik verwurzelt war, Oberbürgermeister der Stadt Hagen. Dieses Amt behielt er, obwohl im Herbst 1946 Kommunalwahlen stattfanden und die CDU stärkste Kraft wurde. Die CDU war mit Steinhoffs integrativer Politik so zufrieden, dass sie darauf verzichtete, das Oberbürgermeisteramt selbst zu besetzen. Für ihr Entgegenkommen erhielt die CDU aber das Amt des Oberstadtdirektors. Steinhoff machte sich sehr um den Wiederaufbau der Stadt Hagen verdient. Sein kommunalpolitisches Engagement zeigt sich zudem darin, dass er von 1950 bis 1956 Vorsitzender des nordrhein-westfälischen Städtetags war und von 1954 bis 1956 im Präsidium des Deutschen Städtetags saß. Zusätzlich zu seinem Oberbürgermeisteramt war Steinhoff Mitglied des westfälischen Provinzialrats und von 1946 bis 1961 Mitglied des Landtags von Nordrhein-Westfalen. Bei den Landtagswahlen holte er für seinen Wahlkreis Hagen I jeweils das Direktmandat. Während seiner Zeit als Landtagsabgeordneter war er vor allem im Haushalts- und Finanzausschuss aktiv, dessen Vorsitz er zeitweise innehatte. Nach dem überraschenden Tod von Ernst Gnoß wurde Steinhoff an dessen Stelle 1949 Minister für Wiederaufbau in Nordrhein-Westfalen. Dieses Amt behielt er bis zur Landtagswahl 1950. In dieser kurzen Amtszeit schuf er gesetzliche Rahmenbedingungen für den unbürokratischen Wiederaufbau der Städte; allein 125.000 Wohnungen konnten in dieser Zeit neu errichtet und für weitere 60.000 Wohnungen die Finanzierung bereitgestellt werden. Aufgrund dieser Erfolge stieg sein Ansehen in der Öffentlichkeit sowie in der SPD-Fraktion erheblich, weshalb Steinhoff darauffolgend stellvertretender Fraktionsvorsitzender wurde.6
Anfang der fünfziger Jahre starben eine Reihe Politiker, die bis dahin die Politik der SPD im Land bestimmt hatten. Zu nennen sind hierbei vor allem Carl Severing († 07.1952), Erik Nölting († 07.1953) sowie der SPD-Fraktionsvorsitzende und Vorsitzende des Bezirks Westliches-Westfalen, Fritz Henßler († 12.1953). Steinhoff folgte Henßler sowohl als Fraktionsvorsitzender als auch als Bezirksvorsitzender nach, was überrascht, da Henßler im Gegensatz zu Steinhoff einen autoritären Führungsstil pflegte. Darüber hinaus war Steinhoff kein exzellenter Rhetoriker und wenig öffentlichkeitswirksam. Es war jedoch der Mangel an Alternativen in der Generation der frühen Landespolitiker, der Steinhoff in diese Positionen brachte, außerdem sprachen seine proletarische Herkunft, sein Aufstiegswille und seine NS-Verfolgung für ihn. Als die SPD mit ihm als Spitzenkandidat in die Landtagswahl 1954 ging, blieb die sozialdemokratische Partei allerdings trotz Stimmengewinn weit hinter der CDU zurück, die mit 41,3% der Stimmen deutliche Wahlsiegerin wurde.7 Zwei Jahre später wurde Steinhoff jedoch der erste sozialdemokratischen Ministerpräsident Nordrhein-Westfalens.