United, he scored eight goals in all competitions – the first coming against Chelsea in the FA Charity Shield in August 1997. He remained with them until his contract expired at the end of the 2001–02 season, when he was given a free transfer. In 2002, Johnsen and fellow Norwegian international Øyvind Leonhardsen had a trial at German side Schalke 04. After that move fell through, Johnsen signed with Aston Villa. In two years at Aston Villa, he scored once in the league, against Leeds United in February 2004. After leaving Aston Villa, Johnsen was offered a trial at Southampton and played against Chievo Verona in a friendly, ultimately he could not agree terms with the club. Johnsen then signed for Newcastle United but only played a handful of games before being released with concerns over his fitness levels. In February 2005, Johnsen announced his retirement from professional football. Shortly afterwards he changed his mind, signing a one-year contract with the Norwegian club Vålerenga. Subsequently, he renewed this contract three times for the following 2006, 2007 and 2008 seasons. Johnsen retired as an active football player on 3 November 2008, with Vålerenga losing their final game of the 2008 season 1–0 to SK Brann. International career Johnsen did not represent Norway at youth level; but while Johnsen was playing for Eik at the second tier, national team coach Egil Olsen, because of a recommendation from Nils Johan Semb, included Johnsen in his squad without having seen him play. Johnsen made his debut for the Norwegian national team in a friendly match against Sweden in 1991. He played as winger, striker and midfielder during his early career at the national team, before he was used primarily as a centre-back. Johnsen played some of the matches in the qualification for the 1994 FIFA World Cup, and played as a striker when Norway won 3–0 away against Poland in 1993 and qualified for the World Cup, but was left out of the squad that travelled to the United States. Four years later, Johnsen was first choice at centre-back, and played all four matches in the 1998 FIFA World Cup. Johnsen played 61 matches for Norway, until May 2004 when he played against Wales. Three years later, he made a comeback for the national team, and played the whole match home against Argentina, which was Johnsen's last match at international level. He was 38