After decades of being subjects of the Tooro Kingdom, the Konjo and Amba peoples asked the British colonial government in Uganda to provide them their own district in the 1950s, separate from the Toro District. The colonial authorities denied their request, and the Bakonjo and Baamba subsequently launched a low-intensity guerrilla war againstthe government in response. In the 1960s, the movement began to shift its objective from creating a separate district to creating a fully independent kingdom, and on 30 June 1962, the movement declared an independent Kingdom of Rwenzururu with Isaya Mukirania as king, three months before the independence of Uganda. The violence reached its height in 1963 and 1964, when Tooro soldiers massacred Bakonjo and Baamba as they sought control over the lower valleys. The Ugandan army intervened against the Rwenzururu, doing such significant damage that the movement was suppressed for some time. One of the units that took part in the suppression of the Rwenzururu movement was the Ugandan 1st Battalion. After the Uganda–Tanzania War and the collapse of the regime of Idi Amin in 1979, Rwenzururian fighters looted abandoned weapons and supplies left by the retreating Ugandan army, reestablishing themselves as a serious threat in the region. However in 1982, the administration of President Milton Obote negotiated a settlement with the leaders of the movement, in which they agreed to abandon the goal of secession in exchange for "a degree of local autonomy", the appointment of Bakonjo and Baamba to government administrative posts, and economic benefits such as vehicles and educational scholarships distributed by local elders. During the negotiations, the government preferred direct talks, as they believed third-party mediation would give legitimacy to the Rwenzururu claim. Amon Bazira, who was a key supporter of the movement to overthrow Idi Amin, had been a key person in the negotiations between the Rwenzururu movement and the Obote government. His belief was that the movement was a largely middle class organisation that could be appeased with commercial prizes. Bazira later approached President Mobutu Sese Seko of Zaire and President Daniel arap Moi of Kenya, both of whom had grounds for disliking the new Ugandan government led by Yoweri Museveni, and asked for support for a new Bakonjo-led rebellion under an organisation called the National Army for the Liberation of Uganda. In 1993, Bazira was assassinated at the State House of Kenya in Nakuru, a probable target of Ugandan agents. In 1995, Sudanese agents engineered the merging of the remnants of NALU with the Uganda Muslim Liberation Army and the Buganda monarchist Allied Democratic Movement in order to give these latter organisations a local constituency, creating the Allied Democratic Forces.
