Heinrich Fehlis nacque il 1° novembre 1906 a Wulften.
Studiò legge esercitando poi l'avvocatura. Istruito, parlava fluentemente inglese e francese.
Si iscrisse al Partito Nazionalsocialista il 1° maggio 1933. Militò dapprima nelle SA per poi passare alle SS.
Venne impiegato a Berlino all'RSHA e successivamente responsabile SD (controspionaggio) per la città di Stuttgart.
Partecipò all'annessione dell'Austria nel 1938 come parte di un Einsatzkommando incaricato di "ripulire" l'Austria dagli oppositori politici in modo segreto.
Ebbe lo stesso incarico comandando l'Einsatzgruppe 1 "Norwegen" che nel 1940 operò operazioni segrete al seguito delle truppe d'invasione tedesche.
In questo incarico venne affiancato dal suo vice Oskar Podlich.
Terminate queste operazioni venne nominato da Wilhelm Rediess comandante (BdS) delle SS e della Polizia in Norvegia. In questo senso fu il responsabile operativo delle attività contro la resistenza e contro la Comunità Ebraica come superiore di Hellmuth Reinhard.
Istituì quattro comandi locali tra i quali per ferocia si distinse quello di Trondheim comandato da Gerhard Flesch.

All'arrivo delle truppe alleate in Norvegia si suicidò l'11 maggio 1945.