In 1854 he was appointed Governor of Cape Colony and High Commissioner for South Africa. Here his principal task was to protect and pacify the eastern Cape frontier against a surging mass of disorderly Kaffir tribes. Supported by a large British army and a small annual parliamentary grant of £40,000, he planned to reorganise the tribal life of the buffer province of British Kaffraria under European Magistrates, civilise the African population by means of schools, hospitals, and employment (his old New Zealand formula), and introduce several thousands of white farmers to stiffen the defence of the frontier and provide work, and a good example, for the natives. But he miscalculated the amount of agricultural land available — the province was already over populated — and he seemed not to appreciate that amalgamation of the races must jeopardise white predominance. He wanted British immigrants, but South Africa did not attract them. After the Crimean War, the Colonial Office sent out 3,000 men of the German Military Legion, but they proved quite unsuitable as colonists and the venture was a fiasco.

Meanwhile, the Kaffirs became excited. War was pending between Basutoland and the Orange Free State. Prophets arose predicting the resurrection of defunct tribal ancestors and a new era of youth, beauty, and plenty for all black people who killed their cattle and stopped planting corn. Grey suspected that those chiefs who ordered obedience to the prophet were plotting to use famine as an excuse for war, and he instituted not only relief schemes but also stern police measures. The result of this fantastic episode (1856–57) was the devastation of British Kaffraria and the adjoining Transkeian country, the reduction of its native population to one-third, and the arrest and disgrace of the offending chiefs, and the abject submission of the others. Some 30,000 refugees were removed into the Western Province of the Cape, the Gcalekas were driven out beyond the Bashee River, and white farmers moved in to occupy the “empty” land. Grey's dispatches persuaded the Colonial Office that this was civilisation, and he wanted the system extended throughout Kaffraria, Natal, and Zululand.

Grey incurred official displeasure by sending too few regiments to India during the Mutiny (1857–58), keeping the German Legion mobilised at British expense, and overspending his British Kaffraria account during the 1856 crisis. He did not take kindly to criticism. The tone of his communications to London became curt, truculent, and defiant, and he lost the confidence of one Secretary of State after another. His crowning fault came when, contrary to orders, he broached the question of confederation with the Orange Free State. The idea had much to commend it, but he was trying to initiate a forward policy when the British Government was resolved on economy and withdrawal from responsibilities. He was recalled by Lytton in 1859, but was reinstated by the Duke of Newcastle with a warning that he must obey orders — a thing he never learned to do graciously. He once told his General that his duty to the Queen impelled him “to disregard or to act contrary to orders issued from the other side of the world, in entire ignorance” of local circumstances, and to treat them merely as “general indications of a line of policy” to be interpreted and modified at his discretion. But his independence went beyond any reasonable discretion that the Colonial Office could tolerate. As one Under-Secretary later wrote, it was impossible to let Grey “claim to hold his authority from the Crown on such terms that he was entitled to refuse obedience to the Home Government”.