Yoweri Museveni
Pemerintahan yang baru mendapatkan dukungan internasional yang luas, dan ekonomi yang telah dirusakkan oleh perang saudara telah mulai pulih setelah Museveni mulai merancang kebijakan-kebijakan ekonomi untuk melawan masalah-masalah penting seperti hiperinflasi dan neraca pembayaran. Dengan meninggalkan gagasan-gagasan Marxisnya, Museveni merangkul penyesuaian struktural neo-liberal yang dianjurkan oleh Bank Dunia dan Dana Moneter Internasional (IMF).
Uganda mulai ikut serta dalam sebuah Program Pemulihan Ekonomi (ERP) IMF pada 1987. Tujuan-tujuannya mencakup pemulihan insentif untuk menggalakkan pertumbuhan, investasi, lapangan kerja, dan ekspor, promosi dan diversifikasi perdagangan dengan tekanan khusus pada promosi ekspor, penghapusan halangan-halangan birokratis dan pencabutan modal dari perusahaan-perusahaan publik yang sakit dengan
tujuan meningkatkan pertumbuhan ekonomi dan pembangunan yang dapat dipertahankan melalui sektor swasta, liberalisasi perdagangan pada segala tingkat.
Setelah Januari 1986, Museveni melanjutkan peranannya sebagai Panglima Tertinggi NRA. Pemerintahan Kenya di bawah Daniel arap Moi mula-mula curiga terhadap apa yang dituduhkan sebagai dukungan pemerintahan NRM yang baru terhadap kelompok-kelompok pembangkang Kenya. Ketegangan memuncak dalam suatu pertikaian militer tanpa kekerasan di Busia di perbatasan Kenya-Uganda pada akhir 1987. Bila
saja perbatasan dengan Kenya ditutup, hal itu akan sangat merusakkan ekonomi Uganda yang tidak memiliki akses ke laut, karena jalur ke Samudra Hindia melalui pelabuhan di Mombasa tergantung pada Kenya.
Dalam perang gerilya mereka melawan pemerintahan Milton Obote, Tentara Perlawanan Nasional merekrut siapapun juga yang mau berperang, tak peduli kebangsaannya. Penganiayaan di tangan rezim Obote mendorong banyak orang Rwanda yang hdiup di pembuangan di Uganda untuk bergabung dengan NRA. Beberapa tahun setelah Museveni memerintah, tentara Uganda masih memiliki beberapa ribu orang Rwanda dalam daftar bayaran mereka. Pada malam 30
September 1990, 4000 anggota NRA bangsa Rwanda secara rahasia meninggalkan barak mereka, dan bergabung dengan pasukan-pasukan lain untuk menyerang Rwanda dari wilayah Uganda. Belakangan diketahui bahwa Front Patriotik Rwanda (RPF) mengoperasikan suatu pasukan yang besar jumlahnya di dalam NRA dengan menggunakan struktur sel gelap.
RPF adalah sebuah gerakan dari orang-orang Rwanda di pembuangan yang menentang pemerintahan Juvénal Habyarimana yang terkait dengan Museveni dan NRM. Para pemimpin RPF termasuk Fred Rwigema dan Paul Kagame, keduanya orang Rwanda di pembuangan dan para anggota pendiri NRM. Pada tahap-tahap awal dari penyerangan itu, Museveni dan Habyarimana sama-sama sedang menghadiri pertemuan puncak PBB di AS. Konon
tanggal mobilisasi RPF telah ditetapkan untuk memungkinkan Museveni menjauhkan dirinya dari tindakan-tindakan mereka, hingga kelak sudah terlalu terlambat untuk menghentikannya. Pasukan Rwanda berhasil mengusir penyerangan itu setelah tambahan pasukan-pasukan yang sangat besar dari Belgia, Perancis dan Zaire.
Museveni dipersalahkan karena keterlibatannya dalam invasi September 1990 dan/atau tidak mengendalikan tentaranya. RPF menghilang di gunung-gunung Vumba yang merentang di perbatasan Rwanda-Uganda. Pemerintahan Habyarimana menuduh Uganda mengizinkan RPF menggunakan wilayahnya sebagai garis belakang, dan menjawab dengan menembaki desa-desa Uganda di perbatasan. Orang banyak percaya bahwa Uganda membalas dengan tembakan balik, yang
mungkin telah melindungi posisi-posisi RPF. Tembak-menembak ini telah memaksa lebih dari 60000 meninggalkan rumahnya. Meskipun dilakukan perundingan mengenai sebuah pakta keamanan, dimana kedua negara setuju untuk bekerja sama dalam menjaga keamanan di sepanjang garis perbatasan bersama mereka, pemberontak RPF telah menduduki sebagian besar wilayah utara Rwanda pada 1992.
Pada April 1994, sebuah pesawat yang membawa Presiden Habyarimana dari Rwanda dan Presiden Cyprien Ntaryamira dari Burundi ditembak jatuh di atas bandara Kigali. Hal ini mendorong terjadinya genosida Rwanda yang menyebabkan sekitar 800000 orang tewas. Front Patriotik Rwanda menyerbu ke Kigali dan mengambil alih kekuasaan dengan pertolongan tentara Uganda.
Anak-anak Uganda yang menjadi pengungsi karena perang di utara Pada April 1995, Uganda memutuskan hubungan dengan Sudan sebagai protes atas dukungan Khartoum terhadap Pasukan Perlawanan Tuhan (LRA), sebuah kelompok pemberontak yang aktif di Uganda utara. Sebaliknya, Sudan mengklaim bahwa Uganda memberikan dukungan kepada Tentara Pembebasan Rakyat Sudan. Kedua kelompok ini dicurigai beroperasi di seberang perbatasan
Uganda-Sudan yang renggang. Pertikaian antara Uganda dan Sudan berasal sekurang-kurangnya pada 1988. Para pengungsi Uganda mencari perlindungan di Sudan selatan pada masa rezim Amin dan Obote II. Namun, setelah NRM berkuasa pada 1986, banyak dari para pengungsi ini bergabung dengan kelompok-kelompok pemberontak Uganda, termasuk Front Tepi Nil Barat dan belakangan LRA. Dalam waktu yang cukup panjang, pemerintahan Museveni menganggap Sudan sebagai ancaman yang paling serius terhadap keamanan Uganda.
NRM naik ke kursi kekuasaan dengan menjanjikan pemulihan keamanan dan penghargaan terhadap hak-hak asasi manusia. Memang, ini adalah bagian dari program 10 butir NRM, seperti yang dicatat oleh Museveni dalam pidato pelantikannya:
Butir kedua dari program-program kami adalah keamanan manusia dan harta milik. Setiap orang di Uganda harus [mutlak memiliki] keamanan untuk hidup di manapun ia mau. Setiap orang, setiap kelompok, yang mengancam keamanan rakyat kita harus dihancurkan tanpa belas-kasihan. Rakyat Uganda hanya boleh mati karena sebab-sebab alamiah yang berada di luar jangkauan kita, tetapi bukan dari sesama manusia yang terus berjalan di panjang dan lebarnya negeri kita.
Meskipun kini Museveni memimpin pemerintahan yang baru di Kampala, NRM tidak dapat memproyeksikan pengaruhnya sepenuhnya di seluruh wilayah Uganda, karena ia ternyata harus memerangi sejumlah pemberontakan. Sejak permulaan kepresidenan Museveni, ia mendapatkan dukungan kuat dari wilayah selatan yang berbahasa Bantu dan barat daya, basis Museveni. Ia behasil mendapatkan dukungan
masyarakat Karamojong, sebuah kelompok setengah nomaden di daerah timur laut yang jarang penduduknya yang tidak pernah mempunyai suara politik yang berarti, untuk bersekutu dengannya dengan menawarkan peranan kepada mereka di dalam pemerintahan yang baru. Namun, wilayah utara di sepanjang perbatasan Sudan terbukti lebih bermasalah. Di sub wilayah Nil Barat yang dihuni oleh
suku Kakwa dan Lugbara (yang sebelumnya mendukung Amin), kelompok-kelompok pemberontak UNRF dan FUNA berjuang selama bertahun-tahun hingga gabungan serangan militer dan diplomasi menenangkan wilayah itu; pemimpin UNRF, Moses Ali, menghentikan perjuangannya dan menjadi Wakil Perdana Menteri II. Rakyat dari wilayah utara negara itu memandang bangkitnya suatu pemerintahan yang dipimpin oleh seseorang
dari selatan dengan rasa takut yang mendalam. Kelompok-kelompok pemberontak bermunculan di antara suku Lango, Acholi dan Teso, meskipun mereka kalah jauh dibandingkan dengan kekuatan NRA kecuali di ujung utara dimana perbatasan Sudan memberikan tempat perlindungan yang aman. Pemberontak Acholi Tentara Demokratik Rakyat Uganda (UPDA) gagal menggulingkan pendudukan NRA terhadap wilayah Acholiland, sehingga menyebabkan
munculnya chiliasme dari Gerakan Roh Kudus (HSM) yang putus asa. Kekalahan UPDA dan HSM meninggalkan pemberontakan itu pada kelompok yang kelak dikenal sebagai Tentara Perlawanan Tuhan, yang berbalik melawan suku Acholi sendiri.