In the past decade, the European Union and its member states have invested heavily in a far-reaching, diffuse, and technologized border regime targeting the elusive figure of the clandestine or illegal African migrant. Taking the mismatch between these large investments and the statistically small number of overland irregular migrants as its starting point, this article explores the embodied effects of illegality engendered in the policing of the Euro-African borderlands. Based on fieldwork with West African police forces, aid organizations, and migrants, it focuses on the migration circuit between the Sahel and Spain, where a joint European response to irregular flows was first tried and tested under the umbrella of the EU border agency Frontex. By highlighting the means of detection used to apprehend illegal migrants - from bodily signs to presumed intentions to migrate - the article looks at how an increasingly reified and embodied modality of migrant illegality is produced on the circuit between West Africa and Europe's southern shores. This production of illegality crucially depends on the incentives offered to African forces for participating in European controls. Tensions among African officers over the unequal gains from such incentives and ambivalence over the rationale for controls, I argue, make the transnational policing of clandestine migration a fraught site of state investment and concern.