Prosecution selectivity is one of the most intractable dilemmas in international criminal justice. It is of little surprise, then, that the International Criminal Court’s (ICC) selection of cases has long been subject to critical debate. This article contributes to the literature by analysing the ICC’s selection procedure from the perspective of affected communities. Vis-à-vis this target audience, the article critiques the procedure’s effectiveness against a measure of perceived legitimacy. Using a Rawlsian model of imperfect procedural justice, the analysis explains the specific shortcomings of the Office of the Prosecutor’s (OTP) selection procedure in being sufficiently consistent, impartial and representative. In turn, this lack of procedural fairness may reduce the likelihood that the OTP selections are perceived as legitimate within affected communities. More broadly, the article argues that the OTP is unable to reach the ‘fairest’ possible prosecutorial decisions as to situations or cases — culminating in the conclusion that its selection procedure makes a limited (if any) contribution to the Court’s perceived legitimacy. The article triggers reflection on the Court’s relationship with target audiences and concludes by making practical recommendations directed at improving the OTP’s selection procedure.