The earliest inhabitants of what is now Rwanda were the Twa, a group of aboriginal pygmy hunter-gatherers who settled the area between 8000 and 3000 BC and remain in the country today. Between 700 BC and 1500 AD, a number of Bantu groups migrated into Rwanda and began clearing forests for agriculture. After losing much of their habitat, the forest-dwelling Twa moved to the mountains. Historians have several theories about the Bantu Migrations. According to one, the first settlers were Hutu; the Tutsi 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. In this theory the Hutu-Tutsi distinction arose later as a class distinction, rather than a racial one.
The population coalesced, first into clans (ubwoko) and into about eight kingdoms by 1700. The country was fertile and densely populated, with its kingdoms strictly controlled socially. The Kingdom of Rwanda, ruled by the Tutsi Nyiginya clan, became increasingly dominant beginning in the mid-18th century. From its origins as a small toparchy near Lake Muhazi the kingdom expanded through conquest and assimilation, reaching its zenith under King (Mwami) Kigeli Rwabugiri between 1853 and 1895. Rwabugiri expanded the kingdom west and north, implementing administrative reforms which included ubuhake (where Tutsi patrons ceded cattle—and privileged status—to Hutu or Tutsi clients in exchange for economic and personal service) and uburetwa (a corvée system in which Hutu were forced to work for Tutsi chiefs). Rwabugiri's reforms developed a rift between the Hutu and Tutsi populations.
The Berlin Conference of 1884 assigned the territory to Germany, with imprecise boundaries. When Gustav Adolf von Götzen explored the country ten years later, he discovered that the Kingdom of Rwanda included a fertile region east of Lake Kivu. Germany wanted this region, which was also claimed by Leopold II as part of his own Congo Free State (annexed by Belgium to form the Belgian Congo in 1908). To justify its claim, Germany began a policy of ruling through the Rwandan monarchy and supporting Tutsi chiefs; this system allowed colonisation with few European troops. Yuhi V Musinga, who emerged as king after a succession crisis following the death of his father Rwabugiri and a struggle with Belgian troops, welcomed the Germans and used them to consolidate his power. The territory became the western border of German East Africa. German rule allowed Rwabugiri's centralisation policy to continue, and the rift between Tutsi and Hutu deepened.
Belgian forces took control of Rwanda and Burundi during World War I, and the country came under Belgian control in a 1919 League of Nations mandate, named Ruanda-Urundi. Although Belgium initially continued the German method of government through the monarchy, in 1926, it began a policy of direct colonial rule in line with the norm in the Congo. Reforms included simplifying the complex three-chieftain system, so one chief (usually Tutsi) instead of three (typically split between Tutsi and Hutu) ruled a local area. Belgian reforms also extended uburetwa (forced labour by Hutus for Tutsi chiefs) to individuals, not just communities, and to regions not previously covered by the system. Tutsi chiefs began a process of land reform with Belgian support; grazing areas traditionally controlled by Hutu collectives were seized by Tutsi and privatised with minimal compensation.
Beginning in the late 1920s, the role of the Catholic Church grew. This was encouraged by the Belgian government, since the priests knew the country well and facilitated its administration. Many Rwandans (including elite Tutsi) converted, since Catholicism was an increasing prerequisite for social advancement. King Musinga refused to convert, and in 1931 he was deposed by the Belgian administration; his eldest son, Mutara III Rudahigwa, succeeded him and eventually became Rwanda's first Christian king. During the 1930s the Belgians introduced large-scale projects in education, health, public works and agricultural supervision, including new crops and agricultural techniques to improve food supply. Though Rwanda was modernised the Tutsis remained in power, leaving the Hutu disenfranchised and subject to large-scale forced labour. In 1935 Belgium introduced identity cards, labelling an individual as Tutsi, Hutu, Twa or Naturalised. Although wealthy Hutu had previously been able to become honorary Tutsi, the identity cards ended further social mobility.