This article examines the ways in which both colonial and postcolonial migration regimes in Kenya and Tanzania have reproduced forms of differential governance toward the mobilities of particular African bodies. While there has been a growing interest in the institutional discrimination and “othering” of migrants in or in transit to Europe, comparable dynamics in the global South have received less scholarly attention. The article traces the enduring governmental differentiation, racialization, and management of labor migrants and refugees in Kenya and Tanzania. It argues that analyses of contemporary policies of migration management are incomplete without a structured appreciation of the historical trajectories of migration control, which are inseparably linked to notions of coloniality and related constructions of (un)profitable African bodies. It concludes by recognizing the limits of controlling Africans on the move and points toward the inevitable emergence of social conditions in which conviviality and potentiality prevail.