Though we did not call him, his larger-than-life persona continues to loom large over our democracy and the country's political landscape.
Delivering his first public speech as a free man at a rally in Cape Town on February 11 1990, Mandela said: "I greet you all in the name of peace, democracy and freedom for all. I stand here before you not as a prophet but as a humble servant of you the people. Your tireless and heroic sacrifices have made it possible for me to be here today. I therefore place the remaining years of my life in your hands."
You might wonder what has given rise to these reflections.
This week I was interviewed by journalists from French television station 1Tele. They asked me what Mandela meant to South Africa.
What came to my mind was the humility and selflessness carried in the message he delivered to those who came out in droves to listen to his maiden public speech.
Mandela, I explained, was a leader with an innate ability to make the right estimate of himself.
Despite being held in high esteem for his commitment to the freedom of his people, he did not have any sense of self-importance.
I also reminded the journalists of Mandela's commitment to reconciliation. This he showed without undermining the experiences of those who bore the brunt of racism in apartheid South Africa.
It was, after all, Mandela who said: "True reconciliation does not consist merely in forgetting the past."
His understanding of reconciliation was that those who were seen as either perpetrators or beneficiaries of apartheid should also come to the party and help build a new united nation.
What also came to my mind was that Mandela also endeared himself to South Africa by deciding to step down after serving only one presidential term.
In doing so he lived up to the dictum: "Great leaders gain authority by giving it away."
These, I explained, were the things that made South Africans see Mandela as an icon who encapsulated what it meant to be a true leader.
The next question I was asked was how I, as a South African, felt about the future of South Africa after Mandela. My response was that I am proud of what South Africa has achieved in the past 15 years of democracy.
I pointed out that under Mandela South Africa was put on the route to democracy, but what the country has since achieved was to put in place institutions that would make it possible for democracy to thrive.
These were created in the spirit of our Constitution that enshrines the basic tenets of democracy including a culture of human rights, political freedom and freedom of expression.
Also enshrined in the Constitution is a separation of powers in government as well as the independence of the judiciary.
It is the creation of institutions like the South African Human Rights Commission, the Equality Court, the Gender Commission and the Public Protector that make me feel optimistic about our democracy.
Having said so, I pointed out that what remains our national duty as South Africans was to ensure that those with political clout - by virtue of their office - should not be allowed to undermine these institutions.
It was also incumbent on the government to ensure that those who try to use their political power or office to undermine these institutions should face the full wrath of the law.
It was in that spirit that the media had raised concerns about, for example, the defiance displayed by ANC Youth leader Julius Malema against the Equality Court's ruling that he should pay a R50000 fine for the sexist utterances he made against the woman who lodged rape charges against President Jacob Zuma.
In the same way, the media had condemned the recent unlawful arrest of Sowetan journalists.
What the interview with the French journalists did was to make me realise the reality that South Africa has made major strides towards becoming a truly democratic society.
It also made me realise that the ability to abort this noble achievement by leaders such as Mandela lies in our hands.