We initiate the study of the *randomness complexity* of differential privacy, i.e., how many random bits an algorithm needs in order to generate accurate differentially private releases. As a test case, we focus on the task of releasing the results of $d$ counting queries, or equivalently all one-way marginals on a $d$-dimensional dataset with boolean attributes. While standard differentially private mechanisms for this task have randomness complexity that grows linearly with $d$, we show that, surprisingly, only $\log_2 d+O(1)$ random bits (in expectation) suffice to achieve an error that depends polynomially on $d$ (and is independent of the size $n$ of the dataset), and furthermore this is possible with pure, unbounded differential privacy and privacy-loss parameter $\varepsilon=1/\mathrm{poly}(d)$. Conversely, we show that at least $\log_2 d-O(1)$ random bits are also necessary for nontrivial accuracy, even with approximate, bounded DP, provided the privacy-loss parameters satisfy $\varepsilon,\delta\leq 1/\mathrm{poly}(d)$. We obtain our results by establishing a close connection between the randomness complexity of differentially private mechanisms and the geometric notion of "secluded partitions" of $\mathbb{R}^d$ recently introduced and studied by Vander Woude et al. (2022, 2023).