We identify and investigate a fundamental puzzle in contemporary mediation of armed conflicts. Although the preparedness of international mediators has increased, the proportion of armed conflicts that receive mediation has not increased, but decreased. Using quantitative data on the occurrence of mediation between 1989 and 2013, our analysis suggests that this puzzling contradiction cannot be explained by conflicts being more fragmented, intractable or internationalized. Instead, we argue that the puzzling decline of mediation can be explained by a mismatch between supply and demand in the international mediation 'market'. Although there are more mediators available, the rise in the number of conflicts involving Islamist armed actors, coupled with increased reliance on terror-listing, especially since 2001, has placed a growing number of conflicts beyond the reach of international mediators. Our findings challenge the conventional belief that the post-Cold War era is characterized by high mediation rates and point to the need to develop the practice of mediation to maintain its relevance in the contemporary conflict landscape.