Lekota was born in Kroonstad on 13 August 1948, into a working class family where he was the eldest of seven children. Most of Lekota’s schooling was completed in Kroonstad, but he matriculated from St Francis College, Mariannhill, where Steve Biko had completed his schooling just a few years earlier. Lekota got the nickname, "Terror", on the soccer field. He is married to Cynthia and has four children
In 1971 Lekota started at the University of the North, and it was here that he became politically active. He joined South African Student Association (SASO), and when the full-time organiser, Abaham Tiro, had to flee the county in 1973, Lekota took over this position. In September 1974 Lekota was arrested with eight other SASO members for organising celebrations around the independence of Mozambique. He was charged under the Terrorism Act, found guilty and sentenced to six years on Robben Island. While on Robben Island he wrote these words to his daughter:
"Above all then, my dear, I am in prison for the sake of peace for our country and the world. I am in prison so that our generation may leave to yours and later generations a country and a world that has the greatest potential for progress."
On Robben Island Lekota came into contact with other political prisoners who in turn influenced his ideas. He moved towards ideas of non-racialism and away from Black Consciousness ideology.
Lekota was released at the end on 1982, and eight months later attended the launch of the United Democratic Font (UDF). At the launch he was elected national publicity secretary. As a member of the UDF, Lekota faced police harassment and detention. In 1984 he was arrested and released, in 1985 he was arrested again, together with other UDF leaders, and charged with high treason in the long Delmas Trial. Throughout the trial the leaders were not allowed bail. In November 1988 Lekota was one of the four found guilty, and he was sentenced to twelve years in prison. He was acquitted on appeal to the Supreme Court.
When the African National Congress (ANC) was unbanned, Lekota became involved with it. He was elected chairperson of the Southern Natal Region, and then of the Northern Free State Region. In 1991 he was elected to the NEC of the ANC, where he worked as chief of intelligence. In 1994 Lekota became the Premier of the Free State, a position he held until 1996. In 1997 he became the first chairperson of the new National Council of Provinces, and in 1999 he was appointed Minister of Defence.
In May 2003 Lekota was sanctioned by parliament for failing to disclose his business interests. As punishment he received a written reprimand and was fined one week’s salary. The opposition parties objected to this punishment saying it was insufficient.