Sexual Minorities Uganda foi fundada por Victor Mukasa, un activista tresxéneru, el 3 de marzu de 2004, en Kempala, nel restorán y café d'Internet Kaival. Ente los primeros miembros taben Val Kalende, Kamuhangire.Y y David Kato, que formaron parte de la primer directiva. Los miembros de SMUG xeneraron discutiniu pol so activismu y tuvieron problemes llegales mientres la mayoría de la hestoria de la organización.