Since then, he has had a black eye and a back problem from being beaten up in a police cell, spent six years in jail for sodomy and corruption and caused the ruling Barisan Nasional (BN) to lose their two-thirds super majority in parliament twice.
Now 66 and a grandfather, Anwar cuts a trim figure as the parliamentary opposition leader and Pakatan Rakyat de facto chief and remains very much as popular as he was when in government.
"I still remember every second of misery which I endured, what my wife, family and friends went through. I give thanks that it didn't affect my peace of mind and I don't feel hatred towards those who had attacked me.
After he was sacked from public office, Anwar was free for 18 days before being arrested under the Internal Security Act (ISA) and later charged for sodomy and corruption.
On the day Anwar was fired, people from various levels of society including then PAS president the late Datuk Fadzil Mohd Nor visited his official residence across from Prime Minister Tun Dr Mahathir Mohamad's residence in Bukit Ledang to offer their moral support and sympathies.
Anwar then moved to his own residence in the leafy Bukit Damansara suburb, where almost every day until he was arrested, the house was filled with people who came from different walks of life, politicians, lawyers, journalists, foreign diplomats and the man in the street.
"I am thankful to Allah for giving me the opportunity to do something and to choose loyal friends, Fadzil being a good example. And also the present PAS leadership with president Datuk Seri Abdul Hadi Awang, DAP adviser Lim Kit Siang among other friends," Anwar said.
His arrest galvanised the opposition and his supporters, who then joined forces under Fadzil's leadership to form Gerak or Malaysia People's Movement.
Since then, Malaysia's politics has been anything but quiet and peaceful - all due to the fallout of what transpired on September 2, 1998.
For two consecutive elections, BN has lost the key two-thirds majority in Dewan Rakyat and even lost the popular vote in the May 5 general election this year.
Now there is talk of a unity government between BN and Anwar's Pakatan Rakyat (PR) which failed to capture power despite winning the popular vote.
"Firstly, it's untrue we have failed. Last month, I went to Istanbul, Turkey and met with leaders from Syria and Egypt including Sheikh Rashid Al-Ghannouchi from Tunisia. He told me, Anwar, there is no country where an oppressive system can succeed, if there are elections, everything will work out.
"From that point of view, I consider that I have enjoyed a major success. Yes, it's true that we didn't manage to form the government, but if we were to come to power using dirty and underhanded tactics, it wouldn't feel right either," he said.
Anwar also clarified news of a unity government being bargained between BN and PR after the opposition leader confirmed with the Asia Sentinel news portal that there have been overtures lately.
"The question of a unity government never cropped up at all. It has been mentioned, so for me there has to be certain concessions to agree on some basic policies,” he said.
"This is what we have been preaching, this is what I've been preaching since 2008. I still remember my first speech as opposition leader was to voice out calls for a regular dialogue on basic issues, economic, crime prevention among others, because it was very necessary."
But he said the government of the day has its work cut out for it in the present economic circumstances in the world.
"I don't understand how the Umno leaders can live in comfort and think that everything is fine when the statistics tell a different figure," Anwar said.
Going beyond dialogue with BN, Anwar also focused on cooperation among the three parties that make up PR - his PKR, DAP and PAS.
"We have heard views that in the aftermath of the general election, Pakatan Rakyat should continue to progress and not rest on their laurels. I agree, we should increase our cooperation.
"Some parties say DAP is comfortable because of strong Chinese support, that PAS should focus on the issue of Malay voters. For me, this doesn't complicate matters or block our cooperation but in fact, this consensus among Pakatan Rakyat is something which is very critical not just to the party but to the country," he said.
In the interview, Anwar also reiterated that PR was against any new delineation exercise for electoral constituencies until there was a change in leadership in the Election Commission (EC).
"We are firmly opposed to this because it is inconceivable that the Election Commission, with its dirty and tarnished record, is given the responsibility to carry out such a major task. It is illogical and we will fight this to the very end.
“It isn't a question of two-thirds majority but about the credibility of the EC which has to be resolved. The issue of the electoral rolls hasn't been settled until now, they should resolve that issue first. The solution doesn't lie in replacing a commission secretary who is going to retire soon with someone new," he said, adding the senior figures should be replaced and not the secretary. - September 2, 2013.
~ The Malaysian Insider