Kyrgiakos has played for local club Thyella Megalochori, Agios Nikolaos, OFI, Panathinaikos, Glasgow Rangers, Eintracht Frankfurt, AEK and, more recently, Liverpool. Though not the paciest of defenders, Kyrgiakos makes up for this with his tough tackling, immense strength and tremendous ability in the air. In a crucial match against rivals Olympiakos, Kyrgiakos famously provoked opposing striker Giovanni to such an extent that the Brazilian star punched him and was consequently sent off. Panathinaikos went on to win the game and that year's (2004) title. The following January, he joined Rangers on loan with an option for a permanent deal at the end of the season. He initally failed to agree terms with Rangers and held talks with Everton, Portsmouth and Schalke 04 before finally agreeing a one year deal at Ibrox on 30 August 2005. He subsequently moved to Eintracht Frankfurt and the Bundesliga.
In August 2011, Kyrgiakos returned to the Bundesliga this time to play for Wolfsburg.