Originally known as the Vodacom African Challenge, the competition was conceptualised and first played in 1999 as communications giant Vodacom sought to leverage their sponsorship of Soweto giants Orlando Pirates and Kaizer Chiefs.
The first year of the competition saw two of the giants of the African continent invited to the pre-season tournament. ASEC Mimosa, the reigning African champions were joined by Tunisia's Espérance. Orlando Pirates walked away with the trophy after an emphatic 4-1 win over Espérance.
The 2000 tournament began on a sour note when Morocco's Raja Casablanca, the new African champions, withdrew as it was felt that their participation was in conflict with Morocco and South Africa's battle to win the right to host the 2006 FIFA World Cup. Power Dynamos of Zambia were added as a late replacement, joining Ivorians Africa Sport, who held the African Cup Winner's Cup. The final between Orlando Pirates and Kaizer Chiefs failed to live up to pre-match expectations, although it did provide a fascinating battle in midfield. Kaizer Chiefs walked away 1–0 winners.
The 2001 Vodacom Challenge held special meaning for supporters from both Ghana and South Africa. Ghanaian clubs Asante Kotoko and Hearts of Oak were invited to play. The organizers dedicated the tournament to the 43 fans who had died at Ellis Park just a few months before, as well as the 126 people who perished at the Accra Sports Stadium during a match between Hearts and Kotoko just weeks before the Ellis Park tragedy. It was a sobering occasion for all, and a reminder that much was still to be done to ensure the safety of spectators across the continent. The final produced no goals and the match went to penalties with Kaizer Chiefs managing to retain the trophy they won the year before with a 3–2 win on penalties against Asante Kotoko.
Asante Kotoko returned for the 2002 event, where they were joined by Democratic Republic of the Congo outfit St Eloi Lupopo. The final was settled by a single spectacular goal from Musasa and Asante Kotoko became the first foreign side to lift the Vodacom Challenge trophy.
St Eloi Lupopo returned to defend their title in 2003 and were joined by compatriots TP Mazembe. Kaizer Chiefs claimed their third title in the final after winning 3–2 on penalties after a goalless match. It was after this tournament that TP Mazembe's Felix Musasa joined Pirates.
As had been the growing trend over the years, the 2004 Vodacom Challenge was dominated by shoot outs. TP Mazembe were back, this time joined by newcomers AS Vita. The final that pitted Kaizer Chiefs against AS Vita Club was disappointing until the dying minutes of the game when a goal from each side saw the match go to penalties. AS Vita went on to win the shoot-out 4–3.
Defending champions AS Vita and Green Buffaloes of Zambia were invited the next year and both fell at the first hurdle setting up a dream final between Pirates and Chiefs. The final in Durban was a cracking match that provided great entertainment for the expectant crowd. Pirates held on to claim their second trophy after a long six-year wait.
The 2006 edition saw a change in format with Chiefs and Pirates now taking on a European giant, as Manchester United was named to the competition. Chiefs and Pirates each took on United in an exhibition match followed by a derby clash to determine who would play the visiting team in the final. Kaizer Chiefs represented South Africa in the final and after a nail-biting penalty shoot out, Kaizer Chiefs raised the new-look trophy in glory.
Tottenham Hotspur, hoping to emulate Manchester United by visiting South Africa and winning the Premier League the next season, were the international team in 2007. Spurs played Pirates in the final and walked away with the Vodacom Challenge Final.
Manchester United returned in 2008 to avenge their loss to Kaizer Chiefs in 2006. In a hard-fought final, the Manchester United team with big names like Wayne Rooney, Rio Ferdinand and Carlos Tevez lifted the trophy and once again the Vodacom Challenge trophy travelled to distant shores.
The 2010 Vodacom Challenge was skipped, due to the 2010 World Cup being organised in South Africa, during the months of June and July.
Manchester City traveled to South Africa for the first time to be the third English Premier League club to take part in the Vodacom Challenge; City, however, lost to Kaizer Chiefs in the final.