Yoweri Museveni
proporsional lebih sedikit daripada Buganda yang anti-UPC, sehingga partai Obote mendapatkan lebih banyak kekuasaan. Kecurigaan-kecurigaan akan terjadinya kecurangan semakin diperkuat oleh pengumuman Muwanga pada hari pemilu bahwa semua hasilnya harus disahkan dulu olehnya sebelum diumumkan kepada masyarakat. Partai-partai yang kalah menolak mengakui
keabsahan rezim yang baru, sambil menyebutkan penyimpangan-penyimpangan pemungutan suara yang terjadi dimana-mana.
Museveni kembali dengan pendukung-pendukungnya ke pusat-pusat kekuatan mereka di pedesaan di daerah selatan dan barat daya yang didominasi suku Bantu untuk membentuk Tentara Perlawanan Rakyat (PRA). Di sana mereka merencanakan pemberontakan terhadap rezim kedua Obote, yang populer dikenal sebagai "Obote II", dan angkatan bersenjatanya, Pasukan Pembebasan Nasional Uganda (UNLA). Pemberontakan
dimulai dengan serangan ke instalasi militer di distrik Mubende tengah pada 6 Februari 1981. PRA kemudian bergabung dengan kelompok perlawanan yang dipimpin bekas Presiden Yusufu Lule, Pejuang Kemerdekaan Uganda (UFF), untuk membentuk Tentara Perlawanan Nasional (NRA) dengan sayap politiknya, Gerakan Perlawanan Nasional (NRM). Dua kelompok pemberontak lainnya, Front Penyelamatan Nasional Uganda (UNRF) dan Bekas Tentara Nasional Uganda (FUNA), terbentuk di Nil Barat dari sisa-sisa pendukung Amin dan melibatkan pasukan-pasukan Obote.
NRM/A mengembangkan "Program Sepuluh Butir" untuk suatu pemerintahan yang baru, yang meliputi demokrasi, keamanan, konsolidasi persatuan nasional, membela kemerdekaan nasional, membangun ekonomi yang independen, terintegrasi dan swa-sembada, perbaikan pelayanan sosial, penghapusan korupsi dan penyalahgunaan kekuasaan, perbaikan atas ketidakseimbangan, kerja sama dengan negara-negara Afrika lainnya dan ekonomi campuran.
Pada Juli 1985, Amnesti Internasional memperkirakan bahwa rezim Obote telah bertanggung jawab atas kematian lebih dari 300000 warga sipil di seluruh Uganda. Organisasi hak-hak asasi manusia itu telah beberapa kali menghadap pemerintah untuk menuntut perbaikan catatan hak-hak asasi manusia nya yang mengerikan sejak 1982. Pelanggaran hak-hak asasi khususnya sangat jelas terjadi di
daerah Uganda tengah yang dikenal sebagai Segi tiga Luwero. Laporan-laporan dari Uganda pada masa ini menimbulkan kecaman internasional terhadap rezim Obote dan meningkatnya dukungan internasional terhadap pasukan-pasukan pemberontak Museveni. Di dalam Uganda sendiri, penindasan yang brutal terhadap pemberontakan telah mempersatukan suku Buganda, kelompok etnis terbesar di Uganda, dengan NRA dalam menghadapi
UNLA, yang dianggap didominiasi oleh orang-orang utara, khususnya suku Lango dan Acholi. Hingga kematiannya pada 2005, Milton Obote menuduh NRA bertanggung jawab atas pelanggaran hak-hak asasi di kalangan suku Luwero.
Pada 27 Juli 1985, perpecahan di dalam pemerintahan UPC menyebabkan terjadinya sebuah kudeta militer yang berhasil terhadap Obote oleh bekas komandan Angkatan Daratnya, Letjen Tito Okello, seorang suku Acholi. Museveni dan NRM/A marah karena revolusi yang telah mereka perjuangkan selama empat tahun telah "dibajak" oleh UNLA, yang mereka anggap telah kehilangan
nama karena pelanggaran-pelanggaran hak-hak asasi manusia yang parah pada masa Obote II. Namun, meskipun pihak Museveni bersikap hati-hati, NRM/A akhirnya setuju untuk menghadiri perundingan perdamaian yang diadakan oleh sebuah delegasi Kenya yang dipimpin oleh Presiden Daniel arap Moi.
Perundingan ini, yang berlangsung dari 26 Agustus hingga 17 Desember, berlangsung dengan sangat tidak bersahabat, dan gencatan senjata yang dihasilkannya dibatalkan dalam waktu yang sangat singkat sesudah itu. Kesepakatan terakhir, yang ditandatangani di Nairobi, menyerukan gencatan senjata, demiliterisasi Kampala, integrasi pasukan-pasukan NRA dengan pasukan-pasukan pemerintah, dan digabungkannya pimpinan NRA ke dalam Dewan Militer. Syarat-syarat ini tidak pernah dipenuhi.
Prospek tentang suatu kesepakatan yang langgeng dihalangi oleh sejumlah faktor, termasuk, antara lain, kurangnya pengetahuan yang mendalam pada pihak Kenya mengenai situasi di Uganda dan tidak diundangnya sejumlah pelaku yang relevan di Uganda maupun dari tingkat internasional dalam pembicaraan itu. Akhirnya, Museveni dan sekutu-sekutunya menolak untuk berbagi kekuasaan dengan para
jenderal yang tidak mereka hormati, apalagi sementara itu NRA mampu mencapai kemenangan militer secara mutlak.
Sementara mestinya terlibat dalam perundingan-perundingan perdamaian, Museveni mendekati Jenderal Mobutu dari Zaire dalam upaya menangkal keterlibatan pasukan-pasukan Zaire dalam mendukung junta militer Okello. Namun, pada 20 Januari 1986, beberapa ratus pasukan yang setia kepada Idi Amin disertai oleh militer Zaire memasuki wilayah Uganda. Pasukan-pasukan itu ikut campur di dalam konflik sipil setelah
beralngsungnya latihan rahasia di Zaire dan imbauan dari Okello sepuluh hari sebelumnya. Dukungan Mobutu terhadap Okello merupakan utang yang kelak diselesaikan oleh Museveni bertahun-tahun kemudian, ketika ia memerintahkan pasukan-pasukan Uganda terlibat dalam konflik yang akhirnya menggulingkan pemimpin Zaire itu.
Namun, pada tahap ini, NRA telah mengembangkan momentum yang tidak dapat dihentikan. Pada 22 Januari, pasukan-pasukan pemerintah di Kampala telah mulai meninggalkan pos-pos mereka beramai-ramai sementara pasukan-pasukan pemerontak merebut wilayah di selatan dan barat daya Uganda. Pada tanggal 25, faksi yang dipimpin oleh Museveni akhirnya merebut ibu kota. NRA menggulingkan pemerintahan Okello dan mengumumkan kemenangan esok harinya.
Museveni diangkat sumpah sebagai Presiden tiga hari kemudian pada 29 Januari. "Ini bukanlah sekadar pergantian pengawal; ini adalah perubahan yang mendasar," ujar Museveni setelah upacara yang dipimpin oleh Hakim Agung kelahiran Britania, Peter Allen. Berbicara kepada kerumunan yang terdiri dari ribuan orang di luar parlemen Uganda, preisen yang baru menjanjikan pemulihan demokrasi dan mengatakan: "Rakyat Afrika, rakyat
Uganda, berhak memiliki pemerintahan yang demokratis. Ini bukanlah hadiah dari rezim manapun. Rakyat yang berdaulat haruslah menjadi publik, bukan pemerintah."
Rezim-rezim sesudah Amin di Uganda dicirikan oleh korupsi, sektarianisme dan ketidakmampuan untuk memulihkan ketertiban dan mendapatkan legitimasi rakyat. Museveni harus menghindari pengulangan kesalahan-kesalahan ini apabila pemerintahannya tidak ingin mengalami nasib yang sama. NRM mengumumkan pemerintahan sementara selama empat tahun, yang terdiri dari basis
etnis yang lebih luas daripada pendahulu-pendahulunya. Namun, wakil-wakil dari berbagai faksi ini dipilih langsung oleh Museveni. Kekerasan sektarian yang telah membayang-bayangi sejarah Uganda baru-baru ini diajukan sebagai pembenaran untuk membatasi kegiatan-kegiatan partai-partai politik dan basis-basis pendukung mereka yang khas etnis. Sistem non-partai
tidak melarang partai-partai politik, namun mencegah mereka untuk mengajukan calon-calon mereka secara langsung dalam pemilu. Apa yang disebut sistem "Gerakan" ini, yang menurut Museveni mengklaim kesetiaan dari setiap warga Uganda, kelak menjadi batu penjuru dalam politik selama hampir 20 tahun.
Sistem Dewan Perlawanan, yang dipilih secara langsung pada tingkat kelurahan, dibentuk untuk mengelola urusan-urusan lokal, termasuk distribusi komoditi-komoditi dengan harga pasti secara merata. Pemilihan anggota-anggota Dewan Perlawanan adalah pengalaman langsung pertama yang dirasakan oleh banyak warga Uganda dengan demokrasi setelah berpuluh-puluh tahun mengalami berbagai tingkat otoriterianisme. Peniruan
strukturnya hingga ke tingkat distrik telah dipuji karena telah menolong rakyat pada tingkat lokal untuk memahami struktur-struktur politik pada tingkat yang lebih tinggi.