Born in Herford, Steinhoff studied law from 1910 through 1921 at the Universities of Freiburg, Munich, Königsberg, Berlin, and Münster, earning his doctorate in 1921. From 1921 to 1923, he was active in the Ministry of the Interior and Justice; in 1924 served as Legation Secretary (Legationssekretär) of the Saxon legation in Berlin; in 1925-26 as a government advisor (Regierungsrat) in the administration (Amtshauptmannschaft) of Zittau; in 1927–28 as district chief (Landrat) of Zeitz; and later as a vice president (Regierungsvizepräsident) in Gumbinnen and vice president (Vize-Oberpräsident) in Königsberg.
Politically, he had joined the Social Democratic Party of Germany (SPD) in 1923. Amidst the turmoil of the early 1930s (see Nazi Germany), he was given time off in 1932 and dismissed from government service in 1933. From 1940 to 1945, during World War II, he served as lawyer for a cardboard-box wholesale business in Berlin.
At the end of the war in 1945, he became president of the provincial administration (Provinzialverwaltung) of Brandenburg. He joined the Socialist Unity Party of Germany (SED) in 1946, and from 1946 to 1949 served as Brandenburg's Minister-President and as a member of its state parliament. From 1949-52 he was East Germany's Minister of the Interior; his dismissal at the end of that time was arranged by Walter Ulbricht.
During that time, he was a member of the German People's Council (Deutscher Volksrat) from 1948–49, and from 1950 to 1954 a member of the Volkskammer. Within the SED, he was a member of the central committee of the SED from 1949-54. He also served as a professor of administrative law at Humboldt University in Berlin from 1949-55.
