Le club est fondé en 2003. S'il porte le nom de deux clubs brésiliens (Flamengo et Santos), il porte en revanche les mêmes couleurs que l'équipe nationale d'Argentine. Dès sa première année d'existence, il parvient à atteindre la première division nationale, où il débute lors de l'édition 2004-2005, achevée sur une descente à l'issue du barrage de promotion-relégation. Le retour en deuxième division ne dure qu'un an et l'União réussit par la suite à se maintenir au plus haut niveau jusqu'à la saison 2013-2014 qui voit la formation de Gaborone être reléguée en deuxième division.
Si le club a participé à huit saisons de Premier League, il n'a jamais réussi à s'y imposer, avec tout de même une 3e place en 2008 et 2010. Le premier titre national du club est remporté en 2009 lors de la victoire en finale de Coupe du Botswana face au Botswana Defence Force XI, après un échec en finale lors de l'édition précédente.
Ce succès en Coupe permet à l'União de participer pour la première fois à une compétition continentale, à savoir la Coupe de la confédération 2010. L'expérience tourne court avec une élimination dès leur entrée en lice face aux Mozambicains du CD Costa do Sol.
Parmi les joueurs les plus renommés ayant porté les couleurs de l'União, on peut citer l'international Mogakolodi Ngele, au club entre 2007 et 2011.
