Etter flere års arbeid i utenrikstjenesten avanserte Sevje i 1992 til byråsjef. Han ledet UtenriksdepartementetsAfrika-seksjon fra 1993 til 1994 og var fra 1998 til 2002 sjef for Midtøsten-seksjonen. Han var stasjonert i Israel under arbeidet med den såkalte Oslo-kanalen. I 1995 ble Sevje den første, offisielle diplomatiske representant for Norge til Den palestinske selvstyremyndigheten,[2] da et representasjonskontor ble etablert i Gaza. Han har etter dette vært ambassadør i Syria og Libanon og var 2006–2008 spesialutsending til Midtøsten. Sevje var ambassadør i Damaskus da Norges ambassade ble brent ned av demonstranter i februar 2006.[3]
Fra 2008 var Sevje ambassadør i Sudan. I statsråd 9. april 2010 ble Sevje utnevnt til ambassadør i Israel.[4] Han har tidligere vært chargé d'affaires og ambassaderåd ved samme stasjon.
