The article examines how the Nubi who arrived in Uganda in the 1890s as a British colonial regiment of hired Sudanese soldiers, evolved into an indigenous community of Uganda by 1995. The article attempts to answer a key question: What caused the ever-changing Nubi identity during different historical situations in Uganda? Using oral narratives and information from different archival documents, the article argues that by the time the Nubi were recognized as one of Uganda’s indigenous communities, various factors under different historical contexts, accounted for their ever-changing identity.