Modern human settlement of what is now Rwanda dates from, at the latest, the last glacial period, either in the Neolithic period around 8000 BC, 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 Twa, aboriginal pygmy hunter-gatherers who remain in Rwanda today. Between 700 BC and 1500 AD, a number of Bantu groups migrated into Rwanda, clearing forest land for agriculture. The forest-dwelling Twa lost much of their habitat and moved to the mountain slopes. Historians have several theories regarding the nature of the Bantu migrations; one theory is that the first settlers were Hutu, while the Tutsi migrated later to form 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 organisation in the area was the clan (ubwoko). The clans were not limited to genealogical lineages or geographical area, and most included Hutu, Tutsi, and Twa. From the 15th century, the clans began to coalesce into kingdoms; by 1700 around eight kingdoms existed in present-day Rwanda. One of these, the Kingdom of Rwanda, ruled by the Tutsi Nyiginya clan, became increasingly dominant from the mid-eighteenth century. The kingdom reached its greatest extent during the nineteenth century under the reign of King Kigeli Rwabugiri. Rwabugiri conquered several smaller states, expanded the kingdom west and north, and initiated administrative reforms; these included ubuhake, in which Tutsi patrons ceded cattle, and therefore 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 changes caused a rift to grow between the Hutu and Tutsi populations. The Twa 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 German East Africa, marking the beginning of the colonial era. The explorer Gustav Adolf von Götzen was the first European to significantly explore the country in 1894; he crossed from the south-east to Lake Kivu and met the king. The Germans did not significantly alter the social structure of the country, but exerted influence by supporting the king and the existing hierarchy and delegating power to local chiefs. Belgian forces took control of Rwanda and Burundi during World War I, beginning a period of more direct colonial rule. Belgium simplified and centralised the power structure, and introduced large-scale projects in education, health, public works, and agricultural supervision, including new crops and improved agricultural techniques to try to reduce the incidence of famine. Both the Germans and the Belgians promoted Tutsi supremacy, considering the Hutu and Tutsi different races. In 1935, Belgium introduced identity cards labelling each individual as either Tutsi, Hutu, Twa or Naturalised. While it had previously been possible for particularly wealthy Hutu to become honorary Tutsi, the identity cards prevented any further movement between the classes.
Belgium continued to rule Rwanda as a UN Trust Territory after World War II, with a mandate to oversee independence. Tension escalated between the Tutsi, who favoured early independence, and the Hutu emancipation movement, culminating in the 1959 Rwandan Revolution: Hutu activists began killing Tutsi, forcing more than 100,000 to seek refuge in neighbouring countries. In 1961, the now pro-Hutu Belgians held a referendum in which the country voted to abolish the monarchy. Rwanda was separated from Burundi and gained independence in 1962. Cycles of violence followed, with exiled Tutsi attacking from neighbouring countries and the Hutu retaliating with large-scale slaughter and repression of the Tutsi. In 1973, Juvénal Habyarimana took power in a military coup. Pro-Hutu discrimination continued, but there was greater economic prosperity and a reduced amount of violence against Tutsi. The Twa remained marginalised, and by 1990 were almost entirely forced out of the forests by the government; many became beggars. Rwanda's population had increased from 1.6 million people in 1934 to 7.1 million in 1989, leading to competition for land.
In 1990, the Rwandan Patriotic Front (RPF), a rebel group composed mostly of Tutsi refugees, invaded northern Rwanda, initiating the Rwandan Civil War. Neither side was able to gain a decisive advantage in the war, but by 1992 it had weakened Habyarimana's authority; mass demonstrations forced him into a coalition with the domestic opposition and eventually to sign the 1993 Arusha Accords with the RPF. The cease-fire ended on 6 April 1994 when Habyarimana's plane was shot down near Kigali Airport, killing him. The shooting down of the plane served as the catalyst for the Rwandan Genocide, which began within a few hours. Over the course of approximately 100 days, between 500,000 and 1,000,000 Tutsi and politically moderate Hutu were killed in well-planned attacks on the orders of the interim government.Many Twa were also killed, despite not being directly targeted. The Tutsi RPF restarted their offensive, and took control of the country methodically, gaining control of the whole country by mid-July. The international response to the genocide was limited, with major powers reluctant to strengthen the already overstretched UN peacekeeping force. When the RPF took over, approximately two million Hutu fled to neighbouring countries, in particular Zaïre, fearing reprisals; additionally, the RPF-led army was a key belligerent in the First and Second Congo Wars. Within Rwanda, a period of reconciliation and justice began, with the establishment of the International Criminal Tribunal for Rwanda (ICTR) and the reintroduction of Gacaca, a traditional village court system. Since 2000 Rwanda's economy, tourist numbers, and Human Development Index have grown rapidly; between 2006 and 2011 the poverty rate reduced from 57% to 45%, while life expectancy rose from 46.6 years in 2000 to 59.7 years in 2015.