Johannessen was 2nd at the 1999 Norwegian Championship after losing a blitz tiebreaker to the winner Berge Ostenstad, =2nd at the Norwegian Championships 2001 behind Einar J Gausel and 3rd at the Norwegian Championship (2005), a half point behind joint leaders Simen Agdestein and Magnus Carlsen. He won the 2001 Norwegian Open Championship. His best results in other events have been =1st at the Bermuda Festival 2002 alongside Hikaru Nakamura and Giovanni Vescovi, =1st at the United Insurance 2002 (Dhaka), 1st at the OSS GM 2002 (Oslo), 1st at the Excelsior Cup (2004) and at the Politiken Cup in 2004, and =1st at the Midnight Sun Chess Challenge (2006).

He represented Norway in:

- the Children's Olympiad in 1995

- the Olympiads of 2000, 2002, 2004, 2006 and 2008

- European Team Championships of 2005, 2009 and 2011 and

- the Four Nations Chess Challenge (between Norway, Latvia, Sweden and England) where he won individual gold for the men's 2nd board.

Johannessen has played with his team Oslo Schakselskap in the European Club Cup since 2004, apart from 2008 and 2009. In national leagues, he has participated in the Norway team championship since 2001 and in the Bundesliga since 2002. He has also played in the national leagues of Portugal and Iceland and in the 4NCL.

He is one of the organizer's nominees to play in the World Cup (2013), representing his first foray into the World Championship cycle. He lost to his first round opponent, Hungarian super-GM Peter Leko and was eliminated from the event.

He was coached by Simen Agdestein. He is a columnist at the <Norsk Sjakkblad> and is a lawyer by trade.