In the late 1830s, some 20,000 Ndebele, descendants of the Zulus in South Africa and led by Mzilikazi Khumalo, invaded the Kalanga Rozwi Empire. Many of the Kalanga people were incorporated and the rest were made satellite territories who paid tribute to the Ndebele Kingdom. He called his new nation Mthwakazi, a Zulu word which means something which became big at conception, in Zulu “into ethe ithwasa yabankulu” but the territory was called Matabeleland by Europeans.

Mzilikazi organised this ethnically diverse nation into a militaristic system of regimental towns and established his capital at Bulawayo. He was a statesman of considerable stature, able to weld the many conquered tribes into a strong, centralised kingdom. In 1852, the Boer government in Transvaal made a treaty with Mzilikazi.

However, gold was discovered in Mashonaland in 1867 and the European powers became increasingly interested in the region. Mzilikazi died on 9 September 1868, near Bulawayo. His son, Lobengula, succeeded him as king. In exchange for wealth and arms, Lobengula granted several concessions to the British, the most prominent of which is the 1888 Rudd concession giving Cecil Rhodes exclusive mineral rights in much of the lands east of his main territory. Gold was already known to exist, so with the Rudd concession, Rhodes was able to obtain a royal charter to form the British South Africa Company in 1889.