Machine learning algorithms (ML) are increasingly used to support decision-making in the exercise of public authority. Here, we argue that an important consideration has been overlooked in previous discussions: whether the use of ML undermines the democratic legitimacy of public institutions. From the perspective of democratic legitimacy, it is not enough that ML contributes to efficiency and accuracy in the exercise of public authority, which has so far been the focus in the scholarly literature engaging with these developments. According to one influential theory, exercises of administrative and judicial authority are democratically legitimate if and only if administrative and judicial decisions serve the ends of the democratic law maker, are based on reasons that align with these ends and are accessible to the public. These requirements are not satisfied by decisions determined through ML since such decisions are determined by statistical operations that are opaque in several respects. However, not all ML-based decision support systems pose the same risk, and we argue that a considered judgment on the democratic legitimacy of ML in exercises of public authority need take the complexity of the issue into account. This paper outlines considerations that help guide the assessment of whether a ML undermines democratic legitimacy when used to support public decisions. We argue that two main considerations are pertinent to such normative assessment. The first is the extent to which ML is practiced as intended and the extent to which it replaces decisions that were previously accessible and based on reasons. The second is that uses of ML in exercises of public authority should be embedded in an institutional infrastructure that secures reason giving and accessibility.