Andersen wurde dreimal norwegischer Juniorenmeister und kam bei den Juniorenweltmeisterschaften 1993 in Baselga di Piné auf den 21. Platz im Kleinen Vierkampf. Erstmals im Eisschnelllauf-Weltcup nahm er im November 1994 in Berlin teil, wobei er den 30. Platz über 1500 m errang. Bei der Mehrkampfweltmeisterschaft 1996 in Inzell lief er auf den 23. Platz im Großen Vierkampf und bei den Einzelstreckenweltmeisterschaften 1998 in Calgary auf den 16. Platz über 1000 m sowie auf den 14. Rang über 1500 m. In der Saison 1999/2000 holte er in Heerenveen über 1500 m seinen ersten Weltcupsieg und erreichte mit dem vierten Platz in der Weltcupwertung über 1500 m sein bestes Gesamtergebnis. Bei der Mehrkampfeuropameisterschaft 2000 in Hamar belegte er den sechsten Platz und bei der Mehrkampfweltmeisterschaft 2000 in Milwaukee den 20. Rang im Großen Vierkampf. Zudem errang er bei den Einzelstreckenweltmeisterschaften 2000 in Nagano den 18. Platz über 1500 m und den 16. Platz über 1000 m. In der folgenden Saison wurde er Zehnter in der Weltcupwertung über 1500 m und bei den Einzelstreckenweltmeisterschaften 2001 in Salt Lake City Sechster über 1500 m. Nachdem er zu Beginn der Saison 2001/02 in Berlin über 1500 m seinen zweiten Weltcupsieg holen konnte, kam er dreimal unter den ersten zehn und erreichte damit den sechsten Platz in der Weltcupwertung über 1500 m. Bei der Mehrkampfeuropameisterschaft 2002 in Erfurt errang er den fünften Platz, bei der Mehrkampfweltmeisterschaft 2002 in Heerenveen den 11. Platz im Großen Vierkampf und bei der Sprintweltmeisterschaft 2002 in Hamar den 19. Platz im Sprint-Mehrkampf. Beim Saisonhöhepunkt, den Olympischen Winterspielen 2002 in Salt Lake City, belegte er den 28. Platz über 1000 m sowie den 20. Rang über 1500 m. Im folgenden Jahr lief er bei der Mehrkampfeuropameisterschaft in Heerenveen auf den 13. Platz im Großen Vierkampf und bei den Einzelstreckenweltmeisterschaften in Berlin auf den 19. Platz über 1000 m sowie auf den achten Rang über 1500 m.
In der Saison 2003/04 errang Andersen mit drei Top-Zehn-Platzierungen den achten Platz in der Weltcupwertung über 1500 m, bei der Mehrkampfeuropameisterschaft 2004 in Heerenveen den 12. Platz im Großen Vierkampf und bei den Einzelstreckenweltmeisterschaften 2004 in Seoul den 16. Platz über 1000 m sowie den 15. Platz über 1500 m. In der folgenden Saison holte er in Baselga di Piné in der Teamverfolgung seinen dritten und damit letzten Weltcupsieg und erreichte mit drei Top-Zehn-Platzierungen den neunten Platz in der Weltcupwertung über 1500 m. Beim Saisonhöhepunkt, den Einzelstreckenweltmeisterschaften 2005 in Inzell, gewann er in der Teamverfolgung und über 1000 m jeweils die Bronzemedaille. Außerdem belegte er dort den 22. Platz über 500 m sowie den vierten Rang über 3000 m und bei der Sprintweltmeisterschaft 2005 in Salt Lake City den 16. Platz im Sprint-Mehrkampf. In der Saison 2005/06 kam er mit vier Ergebnissen unter den ersten Zehn erneut auf den neunten Platz in der Weltcupwertung über 1500 m und absolvierte in Heerenveen seinen letzten Weltcup, welchen er auf dem neunten Platz über 1500 m beendete. Bei der Sprintweltmeisterschaft 2006 in Heerenveen belegte er den 31. Platz im Sprint-Mehrkampf und beim Saisonhöhepunkt, den Olympischen Winterspielen 2006 in Turin, den 18. Platz über 1000 m sowie den siebten Rang über 1500 m.
Andersen wurde viermal norwegischer Meister über 1500 m (1998, 2001, 2003, 2006), dreimal über 1000 m (2003, 2004, 2006), zweimal über 500 m (2004, 2006) und einmal im Großen Vierkampf (1996).
Norwegen
Heerenveen
Berlin
Baselga di Piné