Yoweri Museveni
Mandat demokrasi yang baru (1996–2001) > Konflik regional

Di Uganda, ada banyak sekali imigran Rwanda dari etnis Tutsi – yang merupakan bagian yang cukup besar dari pejuang-pejuang NRA. Kelompok pemberontak Front Patriotik Rwanda yang didominasi suku Tutsi dan berbasis di Uganda adalah sekutu-seku erat NRA, dan telah begitu Museveni berhasil mengukuhkan genggamannya di pusat kekuasaan, ia membantu perjuangan mereka. Serangan-serangan yang gagal dilakukan oleh RPF terhadap pemerintahan Hutu di Rwanda pada paruhan pertama tahun 1990-an dari basis-basis di Uganda barat daya. Baru setelah terjadinya genosida Rwanda pada 1994 RPF mengambil alih kekuasaan dan pemimpinnya, Paul Kagame (seorang bekas tentara di pasukan Museveni), menjadi presiden.
Setelah Genosida Rwanda, pemerintah Rwanda yang baru merasa terancam oleh kehadiran bekas tentara-tentara Rwanda dan anggota-anggota dari rezim sebelumnya (di seberang perbatasan Rwanda di Kongo – yang saat itu dikenal sebagai Zaïre) . Para serdadu ini dibantu oleh Mobutu Sese Seko – yang memimpin Rwanda (dengan bantuan Museveni) dan para pemberontak Laurent Kabila untuk menggulingkannya dan mengambil alih kekuasaan di Kongo. (lihat Artikel utama: Perang Kongo I).
Pada Agustus 1998, Rwanda dan Uganda berusaha menyerang Kongo kembali, kali ini untuk menggulingkan bekas sekutu Museveni dan Kagame – Kabila (lihat Artikel utama: Perang Kongo II). Museveni dan segelintir penasihat militer dekatnya saja yang membuat keputusan untuk mengirim Tentara Pertahanan Rakyat Uganda (UPDF) ke Kongo. Sejumlah sumber di tingkat tinggi menunjukkan bahwa parlemen dan para penasihat sipil Uganda tidak dikonsultasikan tentang hal ini, seperti yang diwajibkan oleh konstitusi 1995. Museveni tampaknya berhasil meyakinkan seorang panglima yang mulanya enggan untuk ikut serta dalam usaha ini. “Kami merasa bahwa orang-orang Rwanda yang memulai perang, dan sudah menjadi tugas mereka untuk melanjutkan dan menyeleasikan tugas ini, tetapi Presiden kita mengambil waktu yang lama dan meyakinkan kita bahwa kita mempunyai kepentingan dalam apa yang sedang terjadi di Kongo", demikian dilaporkan dikatakan oleh seorang pejabat senior. Alasan-alasan resmi yang diberikan Uganda untuk intervensi ini adalah untuk menghentikan “genosida” terhadap orang-orang Banyamulenge di Republik Demokratis Kongo, bersamaan dengan pasukan-pasukan Rwanda , dan bahwa Kabila telah gagal memberikan jaminan keamanan di sepanjang perbatasan dan membiarkan Pasukan-pasukan Demokratis Sekutu (ADF) menyerang Uganda dari garis belakang di Kongo. Pada kenyataannya UPDF tidak dikerahkan di daerah perbatasan, melainkan lebih dari 1.000 km di sebelah barat perbatasan Uganda dengan Kongo  dan untuk mendukung para pemberontak Mouvement de Libération du Kongo (MLC) yang berusaha menggulingkan Kabila. Oleh karena itu, mereka tidak dapat mencegah ADF menyerang kota utama Fort Portal dan mengambil alih sebuah penjara di Uganda Barat.
Pasukan-pasukan dari Rwanda dan Uganda menjarah cadangan-cadangan mineral dan kayu yang kaya di negara itu. Amerika Serikat menjawab invasi itu dengan menunda semua bantuan militer untuk Uganda. Hal ini mengecewakan pemerintahan Clinton, yang telah berharap bahwa Uganda akan menjadi pusat dari Inisiatif Tanggapan Krisis Afrika. Pada 2000, pasukan-pasukan Rwanda dan Uganda melakukan tembak-menembak pada tiga kesempatan di kota Kisangani di Kongo, sehingga menimbulkan ketegangan dan merosotnya hubungan antara Kagame dan Museveni. Pemerintah Uganda juga telah dikritik karena memperparah konflik Ituri, sebuah sub-konflik dari Perang Kongo II. Pada Desember 2005, Mahkamah Internasional menyatakan bahwa Uganda harus membayar ganti rugi kepada Republik Demokrasi Kongo atas pelanggaran-pelanggaran hak-hak asasi manusia selama Perang Kongo II.
Di utara, Uganda telah mendukung Tentara Pembebasan Rakyat Sudan (SPLA) dalam Perang Saudara Sudan Kedua melawan pemerintah Khartoum bahkan sebelum Museveni berkuasa. Dukungan yang berlanjut untuk SPLA, yang dipimpin oleh sahahat lama Museveni John Garang, memimpin Sudan untuk mendukung Tentara Perlawanan Tuhan (LRA) dan kelompok-kelompok pemberontak anti-Museveni lainnya pada pertengahan 1990-an. Ketidakamanan dan konflik-konflik yang muncul karena itu telah melahirkan sejumlah besar pengungsi, kematian dan kehancuran di Sudan selatan dan Uganda utara. Hubungan yang menghangat dengan Sudan sesudah itu melahirkan tekad untuk menghentikan dukungan kepada kekuatan-kekuatan yang memusuhi (dari kedua belah pihak) dan pemberian persetujuan kepada uPDF untuk menyerang LRA di Sudan sendiri.