Andersen was called up for the Danish under-21 national team in June 2001, where he immediately displaced the two-years older Rune Pedersen.
Andersen kutsuttiin Tanskan alle 21-vuotiaiden maajoukkueeseen kesäkuussa 2001, jossa hän syrjäytti kaksi vuotta vanhemman Rune Pedersenin.