In 2002, Mthembu was elected Provincial Secretary of the KwaZulu-Natal branch of the South African Communist Party (SACP), the ANC's close ally.[1] Pursuant to the 2009 general election, he was elected to an ANC seat in the KwaZulu-Natal Provincial Legislature, ranked 33rd on the ANC's provincial party list.[3] He left his private-sector job to take up the seat, which he held in parallel with his SACP office.[2] In the 2014 general election, he was re-elected to his legislative seat, ranked 32nd on the ANC's party list.[4] Over the next two years, he was highly critical of the KwaZulu-Natal ANC, particularly in connection with an ongoing campaign to unseat Senzo Mchunu as Premier of KwaZulu-Natal.[5]
When Mchunu was finally removed as Premier in May 2016, he was replaced by Willies Mchunu, who, shortly after taking office, announced a cabinet reshuffle in which Mthembu was appointed to the KwaZulu-Natal Executive Council as Member of the Executive Council (MEC) for Agriculture and Rural Development.[6] Although Mthembu's appointment was viewed as an attempt to appease the SACP,[6] the SACP was critical of the move, saying that it had not been consulted before the reshuffle was announced.[7] Mthembu asked to be given 24 hours to consider the promotion,[5] but ultimately, with the SACP's endorsement,[7] accepted; he was sworn in as MEC on 8 June 2016, a day after the other new MECs.[8]
While Mthembu was serving as MEC, his ongoing support for Jacob Zuma, the incumbent President of South Africa, became a source of political tension, especially as the SACP grew increasingly critical of Zuma. In May 2018, Mthembu caused controversy by inviting Zuma to be his special guest during his budget vote speech in the provincial legislature; opposition legislators staged a walkout in protest of Zuma's presence.[9] Mthembu's closeness with Zuma reportedly strained his relationship with Blade Nzimande, the incumbent national General Secretary of the SACP and formerly a key ally of Mthembu's; Nzimande had been fired from Zuma's cabinet in late 2017.[9][10] It was also reported that Mthembu was likely to face a serious challenge to his incumbency as SACP Provincial Secretary.[11][10] However, when the SACP's next provincial elective conference was held in Pongola in August 2018, he was re-elected unopposed, as was the incumbent Provincial Chairperson James Nxumalo.[9][12]
In the 2019 general election, Mthembu was re-elected to his seat in the provincial legislature, ranked 38th on the ANC's party list.[4] However, he was not re-appointed to the Executive Council under newly elected Premier Sihle Zikalala.[13] Instead, he was elected Chairperson of Committees in the legislature.[2]
In November 2020, he was elected Deputy Speaker of the KwaZulu-Natal Provincial Legislature, serving under Speaker Ntobeko Boyce; he succeeded Mluleki Ndobe, who had died earlier that month, and he was succeeded as Chairperson of Committees by Siboniso Duma.[14] Ahead of the SACP's next provincial elective conference in May 2022, Mthembu's re-election bid was not expected to face any significant opposition.[15]