Fyssas started his career in the Panionios youth academy, achieving his senior debut in the 1990-91 season. After seven seasons in Nea Smyrni, Athens giants Panathinaikos signed him on a five-year contract in 1998. He made his UEFA Champions League debut in the 2000-01 and proved a reliable member of the Pana defence.
In January 2004 he moved to Lisbon with Benfica, where he was to stay for a season and a half, helping the Eagles claim the 2003-04 Cup and 2004-05 League. During this spell came the pinnacle of Fyssas's career: Greece's surprise victory at the 2004 European Championships. He played in all six of Greece's matches (starting five) and displayed a mixture of uncompromising defending and attacking verve on the left flank in the unlikely triumph.
After being allowed to leave Benfica in the summer of 2005, Fyssas made the surprise decision to move to Scotland with Heart of Midlothian (Hearts), despite reported interest from England and Germany. In 2007 he returned to Panathinaikos FC|Panathinaikos]] to end his career suddenly after a few matches.
Fyssas was a regular in the Greek National Football Team, for whom he has been capped 60 times, scoring 4 goals.