On September 12 1868, King Mzilikazi of the Ndebele state died and his remains were put in a cave at Entumbane, on the northern peripheries of the Matopo Hills. It was not clear who would ascend the throne. The heir to the throne was Nkulumane, son of Mzilikazi by the royal wife; but he was mysteriously missing, and all efforts to find him proved unavailing, the heir apparent Nkulumane's fate was shrouded in mystery.
The council therefore assembled together to discuss the question of the succession, and when it was evident that Nkulumane could not be traced, it was decided to offer the crown to Lobengula, a son of Mzilikazi by an inferior wife, and who had proved himself to be brave in battle and cunning in the council. This was accordingly done. Regent Mncumbatha Khumalo installed Lobengula as the next king. The installation took place in 1870. According to Ndebele custom, a new king had to establish his own royal palace and town. Consequently, Lobengula left King Mzilkazi's last capital of Mhlahlandlela to establish his own town, located a few kilometres north east of Mhahlandlela, it was called Gibixhegu.
A section of the Ndebele nation, however, was opposed to Lobengula, possibly stirred up by some instances by other members of the royal family who wished to have the crown for themselves, refused to accept any king but Nkulumane. It was easy to see, therefore, that there was but one way to decide the question, - a fearful battle was to be fought between the two opposing parties, with the result that Lobengula and the warriors supporting him gained the victory, and the rebels were crushed,so much so, that they consented to Lobengula becoming king without further protests.
In 1872 after scoring victory, King Lobhengula renamed his royal town. The name was changed from Gibixhegu to Bulawayo. The name derives from the verb bulala and the locative formative ko-. Bulala means, in the first instance to kill. It also means to oppose, persecute or bother. King Lobhengula was thus referring to the figurative meaning of the word bulala.
He was being opposed and persecuted by his opponents. The town shall be called "the place of he who is persecuted'. Reference is made to one person - the king himself. In essence, the name of King Lobhengula's town was named after that of the first Bulawayo, that of King Tshaka.