Fondata nel 1924, la Federazione Calcistica Ugandese si è affiliata alla FIFA nel 1959. Già prima di allora, però, le Gru mietevano successi a non finire nella Coppa dell'Africa Orientale, vincendo il titolo ben 22 volte dal 1928 al 1963 (nel 1962 ex-aequo con il Kenya). A queste vittorie vanno poi ad aggiungersi i nove successi nella Cecafa Cup - la Coppa dell'Africa centro-orientale - iniziando con la vittoria della prima edizione nel 1973 per finire con l'ultimo titolo, conquistato in Sudan nel 2003.

La prima partita ufficiale della nazionale ugandese risale al 1926, un'amichevole proprio contro il Kenya persa 3-2. La prima partecipazione dell'Uganda ad una manifestazione organizzata dalla FIFA si è avuta quando ha giocato le qualificazioni per i mondiali di Argentina 1978. Partita ad eliminazione diretta contro lo Zambia: vittoria 1-0 in casa ma sconfitta 4-2 nel ritorno e fine del sogno.

Nelle qualificazioni per Mexico 86 la storia si ripete, con gli ugandesi nuovamente vittoriosi contro lo Zambia 1-0 in casa e nuovamente sconfitti con un margine più ampio in trasferta.
Quattro anni più tardi - Italia 90 - un'altra vittoria casalinga per 1-0, questa volta contro il Malawi, precede una sconfitta per 3-1 in trasferta, con conseguente eliminazione delle Gru.
Al primo turno delle qualificazioni per USA 94 è l'Angola ad avere la meglio sui bianchi, mentre per i mondiali francesi del 1998 l'ostacolo insormontabile è la Guinea.

Nelle qualificazioni per i mondiali di Germania del 2006 il sorteggio del primo turno oppone l'Uganda alla Isole Mauritius. La partita di andata, giocata nella capitale Kampala, termina con un rotondo 3-0 per le Gru. Nel ritorno alle Mauritius, però, gli isolani giocano con convinzione e vincono 3-0 con un gol in zona Cesarini. Si va ai supplementari, e quando tutti pensano già ai calci di rigore l'ala sinistra David Obua, il figlio del Presidente della Federazione Ugandese e di gran lunga il miglior giocatore della squadra, segna il Golden Gol che manda le Gru per la prima volta nella loro storia al secondo turno.

Il girone di qualificazione si dimostra estremamente difficile con compagini come il Sud Africa e il Ghana, che sono tra le migliori del continente.
Basterebbe arrivare terzi per qualificarsi alla Coppa d'Africa del 2006, e le cose si mettono subito bene grazie alla vittoria per 1-0 sulla confinante Repubblica Democratica del Congo con gol di Ibrahim Sekajja e al pareggio casalingo 1-1 proprio contro il Ghana. I risultati diventano però ben presto insoddisfacenti, tanto da convincere la Federazione a cambiare C.T. tre volte in pochi mesi. Alla fine, sotto la guida dell'egiziano Mohammed Abbas, la squadra ha concluso il girone di qualificazione mondiale all'ultimo posto con 8 punti in 10 partite. Abbas ha instillato nella squadra un'inedita mentalità offensiva, fatta di passaggi rapidi e lanci lunghi. I risultati si sono visti nella Coppa dell'Africa Nord-Orientale a Dicembre 2005, dove le Gru hanno sepolto gli avversari a suon di gol prima di arrendersi in semifinale all'odiato Rwanda.

Nella primavera del 2006, per ragioni non meglio chiarite, la Federazione decide di esonerare Abbas e di affidare la squadra all'ungherese Laszlo Csaba. Ancora una volta, le prime partite sotto il nuovo CT hanno destato qualche perplessità, ma la campagna per la qualificazione olimpica è iniziata col piede giusto e alla CECAFA Cup in Etiopia l'Uganda è riuscito (un po' fortunosamente) ad arrivare terzo. Alla fine dell'anno, la squadra del 46enne tecnico di Debrecen è arrivata ad un passo dalla qualificazione alla Coppa d'Africa per la prima volta in oltre trent'anni, mancandola per solo un punto a seguito della vittoria del Mali in Togo all'ultima giornata delle qualificazioni.

Il 25 novembre 2007, l'Uganda è stato sorteggiato in girone con Angola, Benin e Niger al primo turno per le qualificazioni ai mondiali del 2010.

Nella classifica FIFA di Novembre 2007, le Gru occupano la posizione numero 94 del ranking mondiale a quota 351 punti, 2 più della Libia e 11 meno della Guiana.
Secondo la classifica Elo, invece, l'Uganda è al posto numero 102 con 1.412 punti, 10 più dell'Algeria ma solo 1 meno del Togo.