Nyathi staeted playing professional football for Dangerous Darkies who were promoted to the NSL in the 1991 season. They were relegated into obscurity after one season in the top flight and "Going Up", as he was affectionately known, joined Orlando Pirates. He became part of the first Bafana Bafana squad upon the country's return to international football in 1992. He moved on to Cape Town Spurs where he won the league and cup double in 1995. He later moved to Europe where he played for a few teams, including FC St. Gallen (Switzerland), Ankaragücü (Turkey), CD Tenerife (Spain) and Cagliari Calcio (Italy).