Humans moved into what is now Rwanda following the last ice age, either in the Neolithic period around ten thousand years ago, or in the long humid period which followed, up to around 3000 BC. Archaeological excavations have revealed evidence of sparse settlement by hunter gatherers in the late stone age, followed by a larger population of early Iron Age settlers, who produced dimpled pottery and iron tools. These early inhabitants were the ancestors of the Twas, a group of aboriginal Pygmy hunter-gatherers who remain in Rwanda today. Between 700 BC and 1500 AD, a number of Bantu groups migrated into Rwanda, and began to clear forest land for agriculture. The forest-dwelling Twas lost much of their habitat and were forced to move on to the slopes of mountains. Historians have several theories regarding the nature of the Bantu migrations; one theory is that the first settlers were Hutus, while the Tutsis migrated later and formed a distinct racial group, possibly of Cushitic origin. An alternative theory is that the migration was slow and steady, with incoming groups integrating into rather than conquering the existing society. Under this theory, the Hutu and Tutsi distinction arose later and was a class distinction rather than a racial one.
The earliest form of social organization in the area was the clan (ubwoko). Clans existed across the Great Lakes region, with around twenty that existed in the area that is now Rwanda. The clans were not limited to genealogical lineages or geographical area, and most included Hutus, Tutsis, and Twas. From the 15th century, the clans began to coalesce into kingdoms. By 1700, around eight kingdoms existed in present-day Rwanda, the largest ones being Bugesera, Gisaka, the northern part of Burundi, and the early Kingdom of Rwanda. The Kingdom of Rwanda, ruled by the Tutsi Nyiginya dynasty, became increasingly dominant from the mid-eighteenth century, as the Kings centralized power and expanded the kingdom militarily, taking control of several smaller kingdoms. The kingdom reached its greatest extent during the nineteenth century under the reign of King Kigeli Rwabugiri. Rwabugiri conquered a number of smaller states and expanded the kingdom west to the shores of Lake Kivu and north into what is now Uganda. He also initiated administrative reforms; these included ubuhake, a cattle clientship which allowed a small number of Hutus privileged status, and uburetwa, a system of Hutu forced labor. Rwabugiri’s changes caused a rift to grow between the Hutu and Tutsi populations. The Twas were better off than in pre-Kingdom days, with some becoming dancers in the royal court, but their numbers continued to decline.
The Berlin Conference of 1884 assigned the territory to Germany as part of Ruanda-Urundi, marking the beginning of the colonial era. It was then united with the German territory of Tanganyika to form German East Africa. Explorer Gustav Adolf von Götzen, who later became Governor of German East Africa, was the first European to significantly explore the country in 1894; he crossed from the south-east to Lake Kivu and met the King. Germany appointed a Resident for Rwanda in 1907, and German missionaries and military personnel began to arrive in the country shortly thereafter. The Germans did not significantly alter the societal structure of the country, but exerted influence by supporting the King and the existing hierarchy and placing advisers at the courts of local chiefs. They also observed and perpetuated the ethnic divisions of the country; they favored the Tutsis as the ruling class and aided the monarchy in putting down rebellions of Hutus who did not submit to Tutsi control. In 1916, during World War I (WWI), Belgian forces defeated the Germans and took control of Ruanda-Urundi.
In 1919, following the end of WWI, the League of Nations declared Rwanda a mandate territory under the control of Belgium. Belgium’s involvement was far more direct than that of Germany; they introduced large-scale projects in education, health, public works, and agricultural supervision. As the population of the country grew, Belgium introduced new crops and improved agricultural techniques to try to reduce the incidence of famine. This was unsuccessful in preventing the Ruzagayura famine of 1943–1944, which claimed the lives of up to one-third of the population. Belgium also maintained the existing class system, promoting Tutsi supremacy. The Belgian authorities considered the Hutus and Tutsis different races and, in 1935, introduced identity cards labeling each individual as either Tutsi, Hutu, or Twa. While it had previously been possible for particularly wealthy Hutus to become honorary Tutsis, the identity cards prevented any further movement between the classes.