Karrierebeginn

Andersen begann seine Karriere beim kleinen Kristiansunder Ausbildungsverein Clausenegen FK wo er unter anderem mit Ole Gunnar Solskjær zusammenspielte.

1996 kreuzten sich ihre Wege wieder, als Andersen seinen ersten Profivertrag bei der damaligen norwegischen Spitzenmannschaft Molde FK unterschrieb, welche zu dieser Zeit mit Arild Stavrum und eben Solskjær zwei weitere Spieler aus Clausenegener-Jugendmannschaften unter Vertrag hatte.

Gleich in seinem Debütjahr konnte er sich daraufhin einen Stammplatz in der Verteidigung erkämpfen und den Vizemeistertitel in den Tippeligaen feiern. In der Folgesaison folgte der Absturz ins Mittelfeld der Liga, ehe man sich 1997, trotz der Verkäufe des damals gefürchteten "Drei-S-Sturm", Stavrum – Solskjær – Sundgot, wieder im Titelkampf zurückfand. Mit den beiden Vize-Meisterschaften in den Spielzeiten 1998 und 1999 prolongierte man den Aufwärtstrend. Dem inzwischen zum norwegischen Nationalspieler herangereiften Andersen wurde ein großer Anteil am Erfolg bescheinigt, was auch an den Interessenten für einen Transfer ins Ausland augenscheinlich wurde.

Vier Spielzeiten bei Wimbledon

Zur Spielzeit 1999/00 erhielt daraufhin der FC Wimbledon den Zuschlag und Andersen wechselte in die Premier League. Unter dem damaligen Wimbledon Trainer Egil Olsen, der neben Andersen mit Kjetil Wæhler, Tore Pedersen, Martin Andresen und Molde-Teamkamerad Andreas Lund, gleich 5 Norweger zur neuen Spielzeit verpflichtet hatte, erlangte Andersen abermals auf Anhieb einen Stammplatz. In Folge startete der Verein gut in die Saison, fand sich aber im weiteren Verlauf schnell im Abstiegskampf wieder. Von den 5 norwegischen Neuverpflichtungen wusste lediglich Andersen zu überzeugen und behielt auch nach der Entlassung von Olsen seinen Stammplatz. Mit einer 2:0-Niederlage am letzten Spieltag gegen den FC Southampton verspielte man jedoch den Klassenerhalt und musste nach 8 Jahren in der Premier League den bitteren Gang in die Zweitklassigkeit antreten.

Eine Spielklasse niedriger folgte das nächste Desaster. Mit dem klaren Ziel sofortiger Wiederaufstieg in die Saison gestartet, fand man sich kurzzeitig auch in der Division One im Abstiegskampf wieder. Zwar stabilisierte sich die Mannschaft im Verlauf der Saison, hatte aber mit dem Aufstieg nichts mehr zu tun und belegte den enttäuschenden Tabellenrang 8. Im Gegensatz zum Großteil seiner Teamkollegen absolvierte Andersen eine hervorragende Saison und erzielte als Abwehrspieler 5 Tore aus dem Spiel heraus. Es folgten einige Vertragsangebote an den Spieler, die jedoch durch das Veto von Wimbledon im Sand verliefen. In den nächsten beiden Spielzeiten fand sich die Mannschaft im Niemandsland der Liga wieder, ohne mit dem Aufstieg in die Premier League etwas zu tun zu haben.

Abwehrchef in Dänemark

Nach Ablauf seines Vertrags entschied sich Andersen in Folge für einen Transfer zum dänischen Erstligisten Aalborg BK. Gleich in seiner Debütsaison führte er die Mannschaft ins dänische Pokalfinale, wo man sich jedoch dem FC København geschlagen geben musste. In den folgenden beiden Saisonen spielte Aalborg im Spitzenfeld der Liga, ohne jedoch um den Titel in den Superligaen mitspielen zu können. Andersen galt als Dirigent der Abwehr und avancierte zu einem Publikumsliebling der Fans. In der Spielzeit 2005/06 hatte er erstmals Verletzungspech und konnte lediglich 7 Ligaspiele absolvieren. Als er aus der Rekonvaleszenz kam, gab er kurz vor Beendigung des Sommertransferfensters bekannt, in der Folgesaison zum Ligakonkurrenten Brøndby IF zu wechseln, was ihm viel Kritik seitens des Vereins einbrachte. Als Grund für den Wechsel gab Andersen an, um den Meistertitel und auf europäischer Ebene spielen zu wollen, was er bei Brøndby besser realisieren könnte.

Im ersten Jahr als Abwehrorganisator von Brøndby stand er mit dem Verein lange an der Tabellenspitze, bis er sich im April 2006 eine schwere Knieverletzung zuzog und verletzungsbedingt für lange Zeit ausfiel. Brøndby verlor daraufhin die letzten Meisterschaftsspiele und wurde hinter dem FC København nur Vizemeister.

In der Folgesaison brauchte Andersen lange um wieder aus der Rekonvaleszenz zu kommen, ehe er für 5 Spiele sein Ligacomeback gab. Danach wurde die Verletzung abermals akut und Andersen fiel für den Rest der Spielzeit aus. Nachdem er auch in der Spielzeit 2007/08 nicht mehr fit wurde, beendete er im März 2007 offiziell seine Karriere.