Born in Sandefjord, Johnsen grew up in Stokke where he played for the local sides Sem IF and Stokke IL during his youth. He started his senior career as a striker in the second tier side Eik-Tønsberg in 1987, but was retrained as a centre back by head coachNils Johan Semb. Johnsen wanted to play as a striker and after he transferred to Lyn ahead of the 1992 season he played as a striker for the club in Tippeligaen. Half-way through the 1994 season, Johnsen transferred to Lillestrøm, where he was used more as a centre back than a striker, before he moved to Beşiktaş in 1995. After a half season in Turkey, Johnsen was approached by Manchester United manager, Alex Ferguson who wanted to sign him. Johnsen turned down the first offer, but transferred to Manchester United during the summer of 1996, and signed a five-year contract with the club. With a fee of £1.2million, Johnsen became the then most expensive Norwegian defender. While at Manchester United, he won 4 league titles, and one FA Cup in 1999 with the club. He was also a part of the team that won the UEFA Champions League in 1999. He covered the central midfield position in Manchester United's away win over Juventus in the semi-final. He also played the whole of the final in Barcelona, this time in defence, alongside Jaap Stam. He has the rare distinction of also winning four medals in four consecutive appearances with the club. He was on the pitch for the title clincher, FA Cup final, and Champions League final in 1999, and because of injury, the 2000 league title clincher against Tottenham Hotspur. Although he fell well short of the 10 appearances required for a title winner's medal in 2000, he received a title winner's medal through special dispensation – similar to the one credited to Dion Dublin for the same reason seven years earlier. The following season, he just met the criteria for a title medal. While at Manchester 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 wing, 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 an obvious choice as a 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 years and 73 days when he was last capped, making him the second-oldest player for the Norwegian national team, only beaten by Gunnar Thoresen.
