The mountainous and largely arid land that came to be Basutoland was populated by San (bushmen, Qhuaique) until the end of the 16th century. From then Bantu-speaking tribes began to migrate into the area, gradually forming various groups including the Basotho (also called Basuti, Basuto or Sotho). The Basotho became the major group in the area as peoples routed by the Zulu (from 1816) fled there.

From around 1820, a local chief, Moshoeshoe, consolidated the scattered people to resist invaders and became King Moshoeshoe I in the 1830s. He established a fortress capital at the inaccessible Thaba Bosiu in the tableland north of the Maluti in 1824 and successfully resisted a Zulu invasion in 1831.

During Moshoeshoe's reign there were a series of clashes with the Boers of the Orange Free State, the British and with other native tribes. Despite a certain amount of success in battle and Moshoeshoe's skillful diplomacy the kingdom lost considerable territory. A treaty had been signed with the Boer of Griqualand in 1843 and an agreement made with the British in 1853 following a minor war. However, the disputes with the Boer over land were revived in 1858 and more seriously in 1865. The Boer had a number of military successes, killing possibly 1500 Basotho soldiers, and annexed an expanse of arable land which they were able to retain following a treaty at Thaba Bosiu. In order to protect his people, Moshoeshoe appealed to the British for assistance, and in March 1868 the land was placed under British protection and the Boer were ordered to leave. A treaty was signed at Aliwal in 1869 between the British and the Boer defining the boundaries of the protectorate, the arable land west of the Caledon River remained in Boer hands and is referred to as the Lost or Conquered Territory. Moshoeshoe died in 1870.

In 1871 the protectorate was annexed to Cape Colony. The Basotho resisted the British and in 1879 a southern chief, Moirosi, rose in revolt. The rising was crushed and Moirosi was killed in the fighting. The Basotho then began to fight amongst themselves over the division of Moirosi's lands. The British extended the Cape Peace Preservation Act of 1878 to cover Basutoland and began to disarm the natives. Sporadic fighting continued until 1882.

Basutoland was removed from Cape Colony and made a crown colony in 1884 as the Territory of Basutoland. The colony was bound by the Orange River Colony, Natal, and Cape Colony it was divided into seven administrative disricts - Berea, Leribe, Maseru, Mohales Hock, Mafeteng, Qacha's Nek and Quthing. The colony was ruled by the British Resident Commissioner, who worked through the pitso (or pilso, national assembly) of hereditary native chiefs under one paramount chief. Each chief ruled a ward within the territory. The first paramount chief was Lerothodi, the son of Moshoeshoe. During the Boer War the colony was neutral towards both forces. The population was around 125,000 (1275), 310,000 (1901) and 349,000 (1904).

When the Union of South Africa was founded in 1910 the colony was still controlled by the British and moves were made to transfer it to the Union. However the people of Basutoland opposed this and when the South African Nationalist party put its racist policies into place the possibility of annexation was halted. In 1959, a new constitution gave Basutoland its first elected legislature. This was followed in April 1965 with general legislative elections.

Basutoland was renamed the Kingdom of Lesotho upon independence from the United Kingdom on October 4, 1966.