Linke's international debut with the Germany national team took place in a 3–0 victory over South Africa, on 15 November 1997. He represented Germany at UEFA Euro 2000 and the 2002 FIFA World Cup. From 1997 till 2004 he played 43 international matches and scored one goal.