Majola's career began as an Administrative Clerk and Clerk of the Magistrate's Court from 1971 to 1974 in the Madadeni district in KwaZulu-Natal, where he conducted "mostly government clerical work including collection of revenue, population registration, writing reports and labour matters." His experience with criminal trials started in Madadeni when he was appointed the District Court Magistrate from 1977 to 1979, following which he was seconded to the Institute for Public Service Training at the University of Zululand as a magistrate and lecturer from 1979 to 1982 - which also coincided with his studies at the university. Majola served as a legal adviser to Theme Committee 3 of the South African Constitutional Assembly that was responsible for drafting the Constitution of South Africa in 1995.
After his academic career Majola moved to Johannesburg in 1996 where he was appointed the National Director of the Legal Resources Centre, which is a non-profit public interest law organisation that defends poor and marginalised people in South Africa. During his time at the LRC he was involved with the Treatment Action Campaign in 2002 in relation to the "constitutional provisions dealing with the right of access by poor people to medical care." In December 2000 Majola was elected to the board of the South African arm of the Open Society Foundations by billionaire and philanthropist George Soros. On the 21st anniversary of the LRC, Majola wrote an article about the significant contributions made by the LRC to the "development of a human rights jurisprudence and the strengthening of constitutional democracy" in South Africa.
In January 2003 Majola left the LRC to become the Deputy Chief Prosecutor at the UN ICTR headquartered in Arusha, Tanzania. His work included supporting the Chief Prosecutor Hassan Bubacar Jallow in "the prosecution of suspects indicted for international crimes of genocide, crimes against humanity and war crimes committed during the Rwandan genocide of 1994." In a report by the Institute of Security Studies on the investigation and prosecution of international crimes, Majola wrote an article on the work of the ICTR and the challenges pertaining to the prosecution of persons accused of "genocide, crimes against humanity and war crimes".
ICTR Assistant Secretary-General
After 10 years as the Deputy Chief Prosecutor of the ICTR, Majola was appointed by Secretary-General of the United Nations, Ban Ki-moon, as the Assistant Secretary-General of the UN and Registrar of the ICTR. His role as Registrar was to support the organs of the ICTR, which are the judges, the Chambers and the Office of the Prosecutor. His duties also included being the head of the ICTR administration where he provided court management services, staff management, administrative support and Majola "handled related litigation within the UN internal justice system." Following the successful conclusion of the mandate of the ICTR and its subsequent closure in December 2015, Majola left his position as the Assistant Secretary-General.
On 2 December 2016 President Jacob Zuma appointed Majola as the chairperson of the South African Human Rights Commission. Majola's seven-year term commenced on 3 January 2017.
