In democracies around the world, deliberative mini-publics, such as citizens’ assemblies, are increasingly used to complement decision-making by conventional representative institutions. Advocates argue that they make decision-making more deliberative, more inclusive and, in turn, more legitimate. In deeply divided contexts, including those emerging from conflict, these features of deliberative mini-publics may enable them to play a particularly valuable role in helping to address issues that otherwise result in gridlock in power-sharing institutions. However, if deliberative mini-publics are to successfully supplement such institutions in these challenging contexts, there are two vital considerations: are there different ways of designing mini-publics that may strengthen or weaken public support for their use, and do members of each salient group hold perceptions towards deliberative mini-publics that are broadly similar or notably different? In this paper, we address these questions using conjoint experiments in two deeply divided cases: one in Northern Ireland and one in Belgium. In the experiments, we investigate the effect of nine distinct design features of mini-publics (from the nature of the policy issue to the decision rule) on legitimacy perceptions – both overall and among majority and minority group members respectively. The findings have implications for designing citizen-based institutions in deeply divided societies.