Essediri experienced a tough start at Tromsø, and was given partial blame for the club's 2001 relegation. The following year he was lent out to the another Norwegian club Bodø/Glimt. When he returned to Tromsø, he was not considered first-team material. However, the arrival of Per Mathias Høgmo as head coach made Essediri the starting right winger in Høgmo's counterattacking style of play. Essediri's pace made him an important figure in setting up Tromsø I.L.'s counterattacks, and he ended the 2004 season being among the top three for assists in the Premier League. Essediri had successfully turned from scapegoat in 2001 to hero in 2004.