Born in Sophiatown, near Johannesburg, Nhlanhla attended the Ikage Primary School in Alexandra and later matriculated from Kilnerton Training Institute. He joined the ANC's youth wing, the ANC Youth League, in 1957. He was elected onto the ANCYL's Transvaal executive a year later. In early 1964, he travelled to the Soviet Union to study, completing a Master's degree in economics in 1969. However he never worked as an economist.
In 1969 he was appointed head of the ANC's youth and student headquarters in Tanzania, a post he served in for five years before being chosen as the organisation's chief representative in Egypt and the Middle East in 1973. In 1978, the ANC posted him to its Lusaka headquarters as national administrative secretary. In 1981 Nhlanhla became a member of the ANC national executive committee.
In 1986, he joined the organisation's intelligence directorate after serving a three-year stint as secretary to the political military council. The following year he became the ANC's intelligence chief, in which capacity, two years later, he was a member of the ANC group headed by Thabo Mbeki which made contact with South Africa's then-apartheid government.
In 1995, Nhlanhla became Deputy Minister in the Justice Ministry, responsible for intelligence affairs. 1999 Nhlanhla was appointed by President Mbeki as Minister of Intelligence.
Joe Nhlanhla, aged 71, died at the Milpark Hospital in Johannesburg, after more than one month in a comatose state. No further details of his death were made public.