Descoberto no Robotron Sömmerda, foi para o Rot-Weiß Erfurt em 1983 e jogou na base do clube até 1988, quando foi promovido ao time principal. Sua estreia como profissional foi em outubro do mesmo ano, na vitória por 3 a 1 sobre o BSG KKW Greifswald, pelas oitavas-de-final da Copa da Alemanha Oriental, enquanto o primeiro jogo do zagueiro na DDR-Oberliga foi contra o Carl Zeiss Jena, em abril de 1989. Linke ainda jogaria por mais 3 temporadas até deixar o Erfurt em 1992, quando foi contratado pelo Schalke 04 após a diretoria dos Azuis Reais ter tomado conhecimento sobre o zagueiro após um jogo da Copa da Alemanha entre o Erfurt e a equipe de Gelsenkirchen.
No Schalke, Linke fez sua estreia na Bundesliga em setembro, no empate sem gols com o Werder Bremen. Em 6 anos de clube, foram 207 partidas e 16 gols, tendo vencido a Copa da UEFA de 1996–97. Em 1998, foi contratado pelo Bayern de Munique, onde viveu o auge de sua carreira: foram 14 títulos conquistados em 7 temporadas pela equipe bávara. Mesmo não tendo feito atuações de alto nível, eram suficientes para que Linke respondesse a seus críticos de que ele não teria capacidade para ser titular na defesa do Bayern. O zagueiro perderia a titularidade apenas em seu último ano, quando o croata Robert Kovač assumiu a vaga, e disputou apenas 11 partidas. Foi titular em 2 decisões da Liga dos Campeões da UEFA, em 1998–99, contra o Manchester United e 2000–01, contra o Valencia, tendo cobrado o pênalti que deu o título europeu ao Bayern.
Final da carreira
Linke recebe cartão vermelho no jogo entre Red Bull Salzburg e Austria Wien, em setembro de 2005.
Em 2005, Linke assinou com o Red Bull Salzburg para jogar o Campeonato Austríaco juntamente com Alexander Zickler, seu ex-companheiro de equipe no Bayern, sendo nomeado capitão do time. Em 2 temporadas, foi campeão austríaco em 2006–07, que foi ainda seu último título na carreira profissional, deixando o clube após não ter seu contrato renovado
Em junho de 2007, o zagueiro decidiu voltar ao Bayern, desta vez para atuar na equipe B, que disputava a antiga Regionalliga Süd. No ínicio de 2008, foi nomeado assistente de Heinz Hochhauser (então diretor de futebol do Red Bull Salzburg), mas continuou em atividade pelo Bayern II até o final da temporada, encerrando a carreira de jogador aos 38 anos.
Seleção Alemã
Linke, que chegou a ser convocado para a equipe olímpica da Alemanha Oriental e jogou alguns amistosos, não chegou a estrear pela seleção principal, que foi retirada das eliminatórias para a Eurocopa de 1992 após a reunificação. A estreia do zagueiro pela Seleção Alemã foi num amistoso contra a África do Sul, vencido pela Nationalelf por 3 a 0 em novembro de 1997, mas ele não foi lembrado por Berti Vogts para a Copa de 1998.
Jogou a Copa das Confederações de 1999, a Eurocopa de 2000 e a Copa do Mundo de 2002 - nesta última, teve papel fundamental em um time que chegou desacreditado após a má campanha na Eurocopa e chegou até a final contra o Brasil, além de ter marcado seu único gol pela seleção na vitória por 8 a 0 sobre a Arábia Saudita, chegando a anunciar o final de sua carreira internacional após a competição, mas que estaria disponível "em caso de emergência" - o que viria a ocorrer em setembro, quando o técnico Rudi Völler convocou o jogador para a partida contra a Lituânia, pelas eliminatórias da Eurocopa de 2004. Linke voltaria a ensaiar uma despedida do futebol de seleções após o jogo, mas o novo técnico da Alemanha, Jürgen Klinsmann, ligou para o zagueiro e pediu para que ele voltasse a vestir a camisa da seleção devido a uma crise de lesões na zaga, e Linke seria convocado para o amistoso contra a Áustria, em agosto de 2004.
Pós-aposentadoria
Após encerrar a carreira de jogador, Linke passou a se dedicar às funções de gestor esportivo do Red Bull Salzburg durante 3 anos, exercendo o mesmo cargo no RB Leipzig entre fevereiro e maio de 2011, quando o ex-zagueiro alegou motivos pessoais para deixar o cargo.
Em novembro do mesmo ano, foi nomeado diretor-esportivo do Ingolstadt, que disputava na época a segunda divisão alemã. Durante a passagem de Linke, a equipe obteve a promoção para a Bundesliga na temporada 2014–15, mas caiu novamente para a 2. Bundesliga em 2016–17 após 2 anos na divisão principal. Voltaria ao Ingolstadt em novembro de 2018, desta vez como consultor de gestão, permanecendo até abril de 2019, quando foi promovido a diretor-esportivo até junho do mesmo ano. Após o rebaixamento para a terceira divisão, Linke deixou o clube.
