His club career started in 1986 in Dinamo Tbilisi. He became known in Western Europe with German team Eintracht Frankfurt, who he joined in 1992. After a couple of successful seasons he gradually found himself struggling for a first team place, and in 1997 he joined Alania Vladikavkaz. After a short time he was bought by English team Manchester City, where he teamed up with fellow Georgians Murtaz Shelia (a former teammate) and Georgi Kinkladze. Tskhadadze's time at the Manchester club was fraught with injury forcing the team to buy other central defenders such as Andy Morrison. In March 2000 he was released from the club. He then played for Lokomotiv Tbilisi and Anzhi Makhachkala until he retired and was appointed head coach for Dinamo Tbilisi.
On December, 2014, he has been appointed as a new coach of Georgia. 
In 1992 he played 6 caps and scored 1 goal for CIS, including one appearance at the Euro 92. The defender later became a part of the recently formed Georgian national team, and played 25 matches in total, captaining the side. His only goal for Georgia came in a 1997 World Cup Qualifier against Poland, and his last match was played on 30 May 1998 against Russia.