The formation of militaries was a key policy under colonial rule, which affords a unique lens for examining colonial era state-building in Africa. This dissertation builds on three datasets on recruitment into the Tirailleurs Sénégalais in the eight colonies of Afrique Occidentale Française or French West Africa (A.O.F.) These datasets cover: a) recruitment in WWI, b) recruitment in the Interwar period, and c) resistance to military recruitment in WWI. Following an overview of these datasets, the dissertation examines three facets of military recruitment. First, it reassesses common beliefs that colonial military recruitment was often shaped by European “martial race” doctrines, and it finds little to no parallel between British recruitment practices and those in the French Empire. Second, the dissertation examines voluntary enlistment as a lens for understanding the hazy divides between “indirect” and “direct” rule. It finds that chiefs had more influence in recruitment policy along borders, and their degree of influence was not shaped by pre-colonial characteristics. Third, the dissertation finds that state-led infrastructure expansion—namely railway development—was associated with higher draft evasion. This suggests coercive capacity was not neatly strengthened by state-led infrastructure.