Kaizer Chiefs midfielder rose from the bench to score a spectacular long range effort in injury time to hand the hosts victory.
The victory came a few months after South Africa beat Cameroon to the cup.
The match started at a cracking pace with Bafana Bafana having two shorts on target in the opening two minutes.
The opening goal came in the eight minute when Bernard Parker gave the hosts the lead after brilian work on the left by Siboniso Gaxa. Parker finished off Gaxa’s cross following inept marking by the Norwegians.
Norway were back in the game 18 minutes later through a Morten Perdersen setpice.
His freekick from outside the area took a wicked deflection on Steven Pienaar and beat Bafana goalkeeper Itumeleng Khune hands down.
From then on the match degenerated into a dour affair with the two sides struggling under the Royal bafokeng Stadium sweltering heat.
The second half was scrappy save for a few efforts by captain Aaron Mokoena and Teko Modise which came close to winning the game for the hosts.
With the game seemingly heading for the dreaded penalty shootout, Tshabalala hit a powerful shot into the net for the winner.
The match, the 15th edition of the Nelson Mandela Challenge, was played in honour of Mandela, one the world’s most iconic politicians.
Among those who attended were ANC president Jacob Zuma and mining magnate Patrice Motsepe as well as officials from FIFA Local Organising Committee.