In light of these developments Pretoria had to decide whether it would stay in the game and bring in more troops. In late December 1975, there were heated debates between Vorster, foreign minister Muller, defence minister Botha, head of BOSS (South African Bureau of State Security) van den Bergh and a number of senior officials as to withdraw or to stay. Zaire, UNITA and the US urged South Africa to stay. But the US would not openly endorse the South African invasion and assure continuing military assistance in case of an escalation. On 30 December Vorster planned to withdraw after the OAU emergency session in Addis Ababa on 13 January to a line 50 to 80 km north of the Namibian border. "In military terms the advance had come to a halt anyway, as all attempts by Battle-Groups Orange and X-Ray to extend the war into the interior had been forced to turn back by destroyed bridges." In early January 1976 the Cubans launched a first counter-offensive driving Foxbat from the Tongo and Medunda hills. The OAU meeting which the South Africans had hopes for finally debated the Angola issue and voted on 23 January 1976, condemning the South African invasion and demandits its withdrawal. Sobered by the Cuban's performance and by the West's cold shoulder, Pretoria chose to fold and ordered the retreat of its troops from Angola.
The sentiment of the Pretoria government at the time was expressed in a speech by Botha before South African parliament on 17 April 1978, in which he charged the US with "defaulting on a promise to give them all necessary support in their campaign to defeat the MPLA" : "Against which neighbouring states have we taken aggressive steps? I know of only one occasion in recent years, when we crossed a border and that was in the case of Angola when we did so with the approval and knowledge of the Americans. But they left us in the lurch. We are going to retell that story: the story must be told and how we, with their knowledge, went in there and operated in Angola with their knowledge, how they encouraged us to act and, when we had nearly reached the climax, we were ruthlessly left in the lurch".
Once the decision was made, South Africa rapidly withdrew its forces towards Namibia. In late January, the SADF abandoned the towns of Cela and Novo Redondo Apart from a few skirmishes the Cubans stayed well behind the retreating South Africans and easily overcoming the remaining UNITA resistance. By early February 1976 the SADF had retreated to the far south of Angola, leaving behind mine fields and blown up bridges. UNITA's capital, Nova Lisboa (Huambo) fell into FAPLA hands on 8 February, the ports of Lobito and Benguela on 10 February. By 14 February control of the Benguala railway was complete and on 13 March UNITA lost its last foothold in far south-eastern Angola, Gago Gouthinho (Lumbala N'Guimbo). It is in this attack that the Cubans for the first time employed their airforce. Four to five thousand SADF troops kept a strip along the Namibian border up to 80 km deep until Angola at least gave assurance that it wouldn't supply bases for SWAPO and that it would continue to supply electricity to Namibia from the Cunene dams. While the Cubans and FAPLA were slowly approaching the southern border, South Africa and Angola took up indirect negotiations about South African withdrawal brokered by the British and Soviet governments. Neto ordered FAPLA and the Cubans to halt at a distance to the border, forestalling a "clash that some feared might trigger an all-out black war to 'liberate' white-ruled southern Africa". In exchange for South African recognition he offered to guarantee the safety of South Africa's 180 million US$ investment in the Cunene hydroelectric complex. On 25 March Botha announced the total withdrawal of South African troops from Angola by 27 March 1976. On 27 March the last 60 military vehicles crossed the border into Namibia.