He rose to the rank of SS-Standartenführer, reporting to Reinhard Heydrich and Ernst Kaltenbrunner in Berlin and Wilhelm Rediess and Josef Terboven in Norway.

[1][4] General Nikolaus von Falkenhorst (Commander of the Wehrmacht in Norway) gave the following description of Fehlis: "[he] was really a quiet, modest man and always very polite to me.

[1] Despite already having a family in Germany, he entered a relationship with a Norwegian woman named Else Johanne Schaug, who gave birth to his daughter Venke Fehlis in January 1945.

[5]Following the German surrender on 8 May 1945 and the end of World War II in Europe, Fehlis and other SS officials attempted to escape capture by Milorg.

He arranged for Gestapo members to be hidden among ordinary soldiers in the Wehrmacht, personally leading a force of around 75 men disguised in Gebirgskorps Norwegen uniforms to a military camp near Porsgrunn.