Phosa was born in Mbombela township, Nelspruit. However, he grew up with his grandfather in a rural area near Potgietersrus (Mokopane). He matriculated at Orhovelani High School in Thulamahashe.
He was one of the first four members of the ANC to enter South Africa from exile in 1990 in order to start the process of negotiation with the National Party government.
As a result of the first fully inclusive democratic elections in 1994, Phosa was appointed as the first premier of Mpumalanga, a position which he held until 1999. During his time in office, Phosa pioneered planning interaction between the private sector and government. He also spearheaded Nelson Mandela's reconciliation initiatives between the government and the Afrikaans speaking community. Phosa was elected as a member of the National Executive Committee of the ANC in 1999.
In 2001, Cyril Ramaphosa, Tokyo Sexwale and Phosa were investigated in connection with an alleged plot to oust Mbeki. They were cleared.
During the 2007 Conference of the ANC (the 52nd National Conference) held in Polokwane in the Limpopo Province, Phosa was elected to the post of Treasurer General for the Organisation.
Since 1999 Phosa has served as a business consultant for various local and international businesses. In addition, Phosa currently holds chairman, vice-chairman or board member positions at more than ten prominent South African institutions and companies, including the University of South Africa, Afrikaanse Handelsinstituut, Special Olympics South Africa, Value Logistics, EOH (Pty) Ltd, SA Golden Leaf and Hans Merensky Holdings.
On november 2013, RCL bid 4 billion rand for TSB, in part of agreement Phosa's family trust will be issued 6.93 million of shares valued 120 million rand.
Phosa published a volume of poetry called Deur die oog van 'n naald (Through the eye of a needle) in 1996 (re-issued in 2009), and speaks nine languages.
Phosa unsuccessfully ran for the post of ANC Deputy President in 2012. Cyril Ramaphosa received 3,018 votes and was elected deputy president of the ANC, convincingly defeating Mathews Phosa, who received 470 votes and Human Settlements Minister Tokyo Sexwale, who received 463. On April 29th 2017, Phosa announced that he had accepted a nomination for the ANC Presidency and would be a candidate at the 54th ANC conference in December.
On June 11th 2017, Phosa officially announced his intention to seek the Presidential nomination in December 2017. Deur die oog van 'n naald (1996, Tafelberg)