Contemporary warfare depends on private security contractors from countries in the Global South. In Sierra Leone, this dependency has produced emerging markets for private military and security companies (PMSCs) seeking to recruit cheap, military-experienced labor. This article explores how demobilized militia and soldiers in Sierra Leone negotiate categorical divides to make themselves employable for private security contracting in Iraq. Based on 19 months of fieldwork tracing militia soldiers as they move between shifting security constellations, the article introduces the notion of “shadow soldiering” to explain the entanglements of public-private spheres and the blurring of boundaries between the visible and invisible that characterize these constellations. While scholarly work on PMSCs has increasingly highlighted the public-private interconnectedness, the article contributes an ethnographically informed perspective on how security contractors on the ground interpret such entanglements and how global security dynamics intersects with the local, everyday practices and processes that facilitate the supply of contractors.