Yoweri Museveni
FRONASA dan penggulingan Amin (1972–1980)

Pasukan-pasukan di pembuangan yang menentang Amin, dan yang umumnya terdiri dari suku Lango dan Acholi, menyerang Uganda dari Tanzania pada September 1972, namun dipukul balik dan mengalami kekalahan besar. Situasi para pemberontak dipersulit oleh perjanjian perdamaian yang kemudian ditandatangani oleh Tanzania dan Uganda, yang isinya melarang kaum pemberontak menggunakan wilayah Tanzania untuk melakukan agresi terhadap Uganda. Museveni untuk waktu singkat bekerja sebagai dosen di sebuah sekolah tinggi di Moshi, di Tanzania utara, namun kemudian memisahkan diri dari oposisi arus utama dan membentuk Front untuk Keselamatan Nasional (FRONASA) pada 1973. Pada bulan Agustus tahun yang sama, ia menikahi Janet Kataha, seorang bekas sekretaris dan pramugari udara dan mereka dikaruniai empat orang anak.
Pada Oktober 1978, Presiden Idi Amin memerintahkan penyerangan ke Tanzania untuk mengklaim wilayah Kagera untuk Uganda. Sejak 24 hingga 26 Maret 1979, Museveni dan FRONASA menghadiri suatu pertemuan orang-orang yang hidup di pembuangan dan kelompok-kelompok pemberontak di kota Moshi, Tanzania utara. Dengan mengatasi perbedaan-perbedaan ideologi, setidak-tidaknya untuk sementara waktu, berbagai kelompok itu membentuk Front Pembebasan Nasional Uganda (UNLF). Museveni ditunjuk menjadi anggota Dewan Eksekutif yang terdiri dari 11 orang, dan diketuai oleh Yusuf Lule. Dewan ini didampingi oleh Dewan Konsultatif Nasional (NCC) dengan satu orang anggota untuk masing-masing dari ke-28 kelompok yang terwakili dalam pertemuan itu. UNLF menggabungkan pasukan-pasukannya dengan tentara Tanzania untuk melakukan suatu serangan balasan yang memuncak dengan penggulingan rezim Amin pada April 1979. Museveni ditunjuk menjadi Menteri Negara untuk Urusan Pertahanan dalam pemerintahan UNLF yang baru. Ia adalah menteri termuda dalam pemerintahan Yusuf Lule. Ribuan pasukan yang direkrut Museveni untuk bergabung ke dalam FRONASA selama perang dipersatukan ke dalam tentara nasional yang baru. Namun mereka tetap setia kepada Museveni, dan hal ini kelak sangat menentukan dalam pemberontakan-pemberontakan di kemudian hari terhadap rezim kedua Obote.
NCC memilih Godfrey Binaisa sebagai ketua yang baru dari UNLF setelah pertikaian internal yang menyebabkan digulingkannya Yusuf Lule pada Juni 1979. Upaya-upaya Binaisa untuk mengonsolidasikan kekuasaan berlanjut dengan cara yang sama seperti pendahulunya. Pada November, Museveni dipindahkan dari Departemen Pertahanan ke Departemen Kerjasama Regional sementara Binaisa sendiri mengambil alih jabatan di Pertahanan. Pada Mei 1980, Binaisa sendiri dikenai tahanan rumah setelah upayanya untuk menyingkirkan Oyite Ojok, kepala staf angkatan darat – dalam apa yang merupakan kudeta de facto yang dipimpin oleh Paulo Muwanga, Yoweri Museveni, Oyite Ojok dan Tito Okello. Sebuah Komisi Kepresidenan, dengan Museveni sebagai Wakil Ketuanya, dibentuk dan dengan cepat mengumumkan rencana-rencana untuk mengadakan pemilihan umum pada Desember.
Museveni yang kini menjadi tokoh yang cukup dikenal secara nasional, membentuk sebuah partai politik yang baru, Gerakan Patriotik Uganda (UPM), yang kemudian memenangkan pemilihan-pemilihan umum. Museveni kemudian bertarung melawan tiga kelompok politik lainnya: Kongres Rakyat Uganda (UPC), yang dipimpin oleh bekas Presiden Milton Obote; Partai Konservatif (CP); Partai Demokratik (DP). Dua petarung utamanya adalah UPC dan DP. Hasil-hasil resmi menyatakan bahwa UPC adalah pemenangnya, sementara partai Museveni, UPM, hanya memperoleh satu di antara 126 kursi yang tersedia. Sejumlah penyimpangan menyebabkan pemungutan suara tidak dapat dipercaya. Dalam perencanaan pemilu, pemimpin komisi yang berkuasa, Paulo Muwanga, mendukung pandangan UPC bahwa masing-masing kandidat harus mempunyai kotak suara yang terpisah. Hal ini ditentang keras oleh partai-partai yang lainnya, yang menyatakan bahwa hal itu akan membuat pemungutan suara mudah dimanipulasi. Konfigurasi batas-batas politik juga mungkin telah menolong UPC. Daerah-daerah pemilihan yang umumnya pro UPC di Uganda utara mempunyai suara yang secara 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 di mana-mana.