It was a time of euphoria in the mid-1990s when the new country was beginning to show its muscle on the international sporting stage. The rugby World Cup was theirs and Rhodes, clean-cut as a new suit, was winning universal admiration for his inspirational work on the cricket field and off it.
Then the Rhodes phenomenon began to run down. He was not getting runs at Test level; the flaws in his technique were being found out. The word was out that his métier was now only to be found in the limited overs game.
Since October, when the side set out on their exhausting itinerary across three continents, Rhodes has played in only two of 11 Tests, scoring 11 in the rain-ruined Sheikhupura game in Pakistan and 25 in the two innings in Adelaide. Yet he appeared in all 22 one-day internationals.
His Test average has slipped below 30 in 30 games, his only century came nearly five years ago and now, approaching his 29th birthday, it has been all too easy for critics to write off this remarkable man as fit only for the short game.
But Bob Woolmer will have none of that. When the South African selectors settle down to choose their team for the first Edgbaston Test, beginning on Thursday, there seems little doubt that the coach will go in to bat heavily for Rhodes's inclusion.
Woolmer says: ``I think Jonty is playing better cricket now than at any stage in his career. He bats with much greater maturity and his shot selection is undoubtedly better than it was.
``Jonty deserves a lot of credit for this. He realised he needed to look at his batting and went away and worked very hard on it. He has shown an awful lot of character in raising his standard.
``It is a personal opinion but I believe he has put himself in contention for a Test place this week. He still has time on his side to develop. With the level of fitness he carries I think his best years as a Test cricketer are ahead of him.''
There is no doubt, as Woolmer stresses, that Rhodes's personality has an enormous and positive influence on the rest of the side. He is not alone in that view. Hansie Cronje feels the bald statistics of Rhodes's Test record reveal little of the impact he has in the heat of battle.
It remains to be seen, however, whether this view will carry the day, with Peter Pollock, the convenor of selectors, believed to favour the claims of Brian McMillan.
Meanwhile, the defeat in the final Texaco game at Headingley could have its rewards, Woolmer feels. ``Maybe we weren't as sharp as we should have been but there's no harm in being kicked in the pants.''
Woolmer has one more year as South African coach and his continued determination to leave then is in part driven by the all-consuming demands of the international game. The father of two teenage children, he has spent only 36 nights at home in Cape Town since last September.
After the 1999 World Cup, he will be looking round for another job in the game in coaching, ``which is my strength''. There is talk of the appointment of a national coach in South Africa and Woolmer does not hide his interest in such a position. ``That would be the first prize. But if I have to earn my living in another part of the world, so be it.''
There has been speculation that he might land the England coaching post if South Africa accomplish a demolition job in the summer's Test series. But he veers away from such talk as if stung. ``I don't want to get involved in that conjecture.''
Surrey made an approach last autumn, Warwickshire might like him back, and Woolmer does not discount the possibility of a return to an English county. ``The future will be dictated in part by the United Cricket Board. If they didn't want me and a county made an offer I would have to look at it.''
But would the man known unkindly as 'Bobby Lap-top' because of his innovatory methods and dexterity with the computer be acceptable to the game's traditionalists here? He seems almost hurt at the suggestion. ``Do some people feel like that about me? Maybe they do. But I'm a traditionalist, too, you know.''