He was born in Mazoka village in the Fort Beaufort district in 1920. He started working at a laundry in Port Elizabeth after leaving school. He became a trade unionist in his youth, and was one of the ANC leaders arrested during the transport boycott of 1952.
Mhlaba joined the ANC and the SACP in 1944 and 1943, respectively. He was the district secretary of the Communist Party from 1946 until it was banned in 1950. He was chairman of the Port Elizabeth branch of the ANC from 1947 to 1953, and was then elected to the Cape Executive committee.
After the ANC was banned he joined other exiles in obtaining military training. Returning to South Africa in 1962, he commanded Umkhonto we Sizwe until 1963, when he was arrested along with other key members at a farm in Rivonia.
He was sentenced to life imprisonment in the Rivonia trial, and served time on Robben Island. In 1982 he was transferred to Pollsmoor. By special permission he married his common-law wife Dedika Heliso in 1986, with whom he had three children.
Nelson Mandela was a witness at the ceremony, conducted in the prison commandant's office. Afterwards Mhlaba was legally permitted to touch his wife for the first time in 22 years.
After his release from prison in October 1989, he was elected to the ANC national executive and the South African Communist Party central committee. He became national chairperson of the SACP in 1995.
In January 1994 he was chosen as the ANC's premier-designate for a unified Eastern Cape. He helped to establish the house of traditional leaders. He then became the High Commissioner to Uganda and Rwanda, until he retired in 2001.
In April 2001 he released a book of his memoirs, narrated by him and researched and compiled by Thembeka Mafumadi.
Mhlaba had a stroke on July 19, 2003, but he recovered quickly.
He is seen as a stalwart member of both the ANC and the SACP, and in recent years his presence has been He was recognised with the Isitwalandwe Award in 1992 for his role in the liberation struggle, and the Moses Kotama Award in 2002 for his contribution to the SACP.