Onder leiding van bondscoach Nils Johan Semb maakte Andersen zijn debuut voor het Noors voetbalelftal op 20 mei1999 in de vriendschappelijke wedstrijd tegen Jamaica (6-0) in Oslo, net als Andreas Lund (Molde FK). Hij viel in dat duel na 79 minuten in voor Steffen Iversen. Andersen speelde in totaal 38 interlands voor zijn vaderland.