Born in Mphahlele, Phatudi initially worked as a teacher and educational administrator before attending the University of Fort Hare, gaining a BA in 1947 and a teaching diploma in 1950 at the University of Witwatersrand, graduating with a BEd in 1965. He was also awarded an Honorary Doctorate from the University of the North in 1973, after which Phatudi encouraged others to use the Dr prefix wherever possible when referring to him.
Phatudi served as President of the Federation of Inspectors of Schools in South Africa from 1958 to 1969 before becoming involved in the nascent Lebowa nation building exercise and had risen in prominence to the extent that when Lebowa was granted self-government on 2 October 1972, Phatudi was appointed Minister for Education before his election as Chief Minister on 8 May 1973. Not one for wasting time settling into the role, Phatudi had been Chief Minister for one day when he informed the South African government that if Lebowa was to become self-sufficient then substantial tracts of South Africa, including a number of white towns, would need to be added to Lebowa territory. The statement was not well received in Pretoria, although they did eventually transfer several small tracts of land to Lebowa.
The earlier outburst aside, Phatudi was considered the most tactful of the bantustan leaders, with a modus operandi directed more at calm negotiations with Pretoria and dissident bodies than the angry outbursts epitomised by leaders like the Transkei's Kaiser Matanzima. However, when these failed, Phatudi was not above unleashing his police against political opponents.
Economic problems continued to plague Lebowa however and Phatudi struggled to maintain control over the increasingly disgruntled homeland population throughout his rule. Phatudi died in office in 1987; Lebowa itself only lasted another seven years before its reintegration into South Africa.