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. In 1921-23 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 (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-45, 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 (SED) in 1946, and from 1946-49 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-54 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.