Uznawany jest za jedną z pierwszych „gwiazd” norweskiej piłki nożnej. W reprezentacji Norwegii w piłce nożnej zadebiutował 17 września 1911 w przegranym 1:4 meczu ze Szwecją – było to dopiero trzecie w historii międzynarodowe spotkanie norweskiej kadry, która osiągała wówczas słabe rezultaty – w pierwszych 20 meczach Andersena w jej barwach zremisowała ona sześciokrotnie, a pozostałe czternaście spotkań przegrała. Andersen wystąpił w pierwszym wygranym przez Norwegię meczu międzynarodowym – 16 czerwca 1918 w Oslo pokonała ona 3:1 Danię (dla samego Andersena był to 21. mecz w drużynie narodowej). Jako pierwszy Norweg w historii osiągnął barierę 25 występów w piłkarskiej reprezentacji, 25. mecz rozgrywając 29 czerwca 1919 w Oslo (wygrana 4:3 ze Szwecją) – za osiągnięcie to, jako pierwszy, w 1930 roku został przez Norges Fotballforbund uhonorowany trofeum Gullklokka. Z reprezentacją swojego kraju dwukrotnie wystąpił w turnieju olimpijskim – w 1912 Norwedzy przegrali 0:7 z Duńczykami i zajęli 5. lokatę, a osiem lat później w 1. rundzie niespodziewanie pokonali 3:1 uznawanych za faworytów do złotego medalu Anglików (występujących pod flagą Wielkiej Brytanii), jednak w kolejnych spotkaniach przegrali 0:4 z Czechosłowacją i 1:2 z Włochami i ostatecznie ponownie zostali sklasyfikowani na 5.