During his time in prison, Maharaj also completed a BAdmin degree, an MBA, and part of a BSc degree.
After being released from the Robben Island prison in 1976, Maharaj was deployed by the ANC to Zambia in 1977. He was elected to the National Executive Committee of the ANC in 1985. From 1988 to 1990 Maharaj worked underground in South Africa as part of the ANC's Operation Vula, which was a project to infiltrate the ANC's top leaders back into South Africa. During this time Maharaj worked with Schabir Shaik's two brothers, Yunis Shaik and Moe Shaik, also members of the ANC. Maharaj reported to the then ANC intelligence chief Jacob Zuma.
In February 2003 the South African newspaper, The Sunday Times, published allegations that Mac Maharaj and his wife Zarina had received more than R500,000 between May 1998 and February 1999 from a businessman, Schabir Shaik, who had shared in two multi-million rand contracts awarded by the Ministry of Transport whilst Maharaj was Minister. In August 2003 Maharaj resigned from FirstRand Bank following the media furor around the allegations of corruption.
In March 2007 the South African newspaper, City Press, published allegations that Maharaj’s wife Zarina opened a Swiss bank account in 1996, and two days after opening it, received over $100,000 into the account from Schabir Shaik. Six months later, in March 1997, the same Swiss account received a further $100,000 from Schabir Shaik.
In November 2011 the South African newspaper The Mail and Guardian attempted to publish further allegations about both Mac and Zarina Maharaj, in relation to their interviews by prosecutors in 2003, but did not do so after Mac Maharaj laid criminal charges against the newspaper for allegedly infringing the laws protecting the secrecy of the 2003 prosecutor interviews.
Maharaj has never been charged by South African prosecutors supposedly because it would have been difficult to prove that Maharaj had corrupt intentions when he and his wife received money from Schabir Shaik.