Though states frequently attempt to formalise and regulate militias, there has been very little research whether or not such a formalisation can, indeed, improve the performance of militias in terms of greater security provision and reduction of abuses against the population. Using original quantitative and qualitative data from North-East Afghanistan, we show that the integration of unregulated anti-Taliban militias into the Afghan Local Police (ALP) in late 2011 and early 2012 has, indeed, led to an improved performance of these militias in the eyes of the population: fear of militias dropped, while their perceived positive security impact increased when compared to their assessment prior to the establishment of ALP.