Fehn nasceu em Kongsberg em Buskerud, Noruega. Ele era filho de John Tryggve Fehn (1894–1981) e Sigrid Johnsen (1895–1985). Ele recebeu sua educação em arquitetura na Escola de Arquitetura e Design de Oslo. Ele iniciou seu curso de estudos em 1946 e se formou em 1949. Entre outros instrutores, ele estudou com Arne Korsmo (1900–1968).[4]
Em 1949, Fehn e o arquiteto Geir Grung (1926–1989) ganharam o concurso para o Edifício do Museu para as Coleções Sandvig em Maihaugen em Lillehammer. Em 1950, Fehn juntou-se ao PAGON (Progressive Architects Group Oslo, Noruega). O grupo, liderado por Arne Korsmo, tinha como objetivo implementar e divulgar a arquitetura moderna.
Em 1952–1953, durante viagens ao Marrocos, ele descobriu a arquitetura vernácula, que influenciou profundamente seu trabalho futuro. Mais tarde mudou-se para Paris, onde trabalhou durante dois anos no estúdio de Jean Prouvé, e onde conheceu Le Corbusier. Em seu retorno à Noruega em 1954, ele abriu um estúdio próprio em Oslo.[5]
Aos 34 anos, Fehn ganhou reconhecimento internacional por seu projeto do Pavilhão Norueguês na 1958 Brussels World Exhibition.[4] Na década de 1960, ele produziu duas obras que permaneceram destaques em sua carreira: o Pavilhão Nórdico na Bienal de Veneza (1962) e o Museu Hedmark em Hamar (1967-1979). Outras obras notáveis incluem o Museu Norueguês do Glaciar em Fjærland (1991-2002) e o Museu Nacional de Arte, Arquitetura e Design de Oslo (2003-08).[6]