Nel MediterraneoIl 23 febbraio 1943, il giorno in cui cade in combattimento - ma per un cedimento strutturale del suo aereo - Joachim Munchenberg, comandante dello JG 77 di base nell'Africa settentrionale si determina un'altra svolta nella carriera di Steinhoff.
Promosso maggiore, viene trasferito dal fronte orientale al fronte mediterraneo per sostituire Munchenberg.
Steinhoff arriva in Africa in marzo, quando le forze italo-tedesche, pressate da sud dall’ 8° Armata di Montgomery e da ovest da quelle poste al comando di Eisenhower , sotto la guida di Rommel stanno tentando un ultimo disperato contrattacco a Medenine, in Tunisia.
La situazione è tutt'altro che brillante:
ormai la perdita dell'ultimo lembo di territorio africano controllato dalle divisioni dell'Asse appare inevitabile (cosa che avverrà il 7 maggio successivo, quando cadranno Tunisi e Biserta).
Steinhoff si vede così affidare il comando di un'unità decimata negli uomini e nei mezzi, costretta a condurre una lotta impari nei cieli contro un nemico sempre più forte.
Ancora una volta le qualità di comandante di Steinhoff si palesano.
Con l'esempio personale riesce a tenere alto il morale dei suoi uomini e a fare dello JG
77 uno dei migliori reparti da caccia tedeschi nello scacchiere mediterraneo.
Anche l'ingrato compito, loro affidato (la scorta agli aero convogli che tentano di portare rifornimenti alle divisioni italo-tedesche isolate in Tunisia) viene svolto dai piloti di Steinhoff ai limiti delle possibilità umane, tenuto conto della schiacciante superiorità aerea alleata.
Caduta la Tunisia, lo JG 77 viene trasferito in Sicilia.
Poi, dopo lo sbarco nell'isola e la conseguente avanzata alleata, comincia anche per l'unità di Steinhoff la progressiva ritirata verso l'Italia continentale.
Di base qui, lo JG 77 viene tra l'altro impegnato contro i bombardieri alleati che dai campi italiani occupati partono per attaccare l'Italia settentrionale e la Germania.
Poi, trasferita nei Balcani, l'unità di Steinhoff entrerà fra l'altro in azione contro i Liberator americani mandati, il 21 aprile 1944, ad attaccare i campi petroliferi romeni di Ploiesti.
Ormai però il fulcro dell'offensiva alleata si va sempre più spostando sulla Germania.
Nel tentativo di combatterla i tedeschi fanno ricorso tra l'altro ai nuovi caccia a reazione Messerschmitt Me 262, un primo reparto dei quali è stato costituito al comando del maggiore Walter Nowotny.
Caduto quest'ultimo l'8 novembre 1944 il Kommando Nowotny viene passato agli ordini di Steinholl (che nell'ottobre precedente era stato richiamato in Germania per affiancare Nowotnv).
Il reparto viene ricostruito come JG 7, di base a Brandemburg-Briest.
Ma, nonostante le sue qualità di comandante e organizzatore, Steinhoff non può far niente nemmeno con i nuovi aerei (con i quali si aggiudica altre sei vittorie).
La sconfitta della Germania nazista è ormai questione di tempo e Steinhoff non ne vive combattendo le ultime ore solo perchè il 18 marzo un incidente al decollo con un Me 262, lo costringe in un ospedale con ustioni piuttosto gravi (dalle quali, per sua fortuna, si rimetterà completamente).
Concluso il conflitto, quando rinascono le forze armate della Germania federale Steinhoff torna alla ribalta (e stavolta in piena luce) ai vertici della Luftwaffe inquadrata nella NATO.
Ritiratosi per raggiunti limiti di età, si è dedicato al giornalismo;
Ha diretto il mensile (Aerospace International) pubblicato a Monaco di Baviera.