The ability to distill quantum coherence is key for the implementation of quantum technologies; however, such a task cannot always be accomplished with certainty. Here we develop a general framework of probabilistic distillation of quantum coherence, characterizing the maximal probability of success in the operational task of extracting maximally coherent states in a one-shot setting. We investigate distillation under different classes of free operations, highlighting differences in their capabilities and establishing their fundamental limitations in state transformations. We first provide a geometric interpretation for the maximal success probability, showing that under maximally incoherent operations (MIO) and dephasing-covariant incoherent operations (DIO) the problem can be further simplified in to efficiently computable semidefinite programs. Exploiting these results, we find that DIO and its subset of strictly incoherent operations (SIO) have equal power in probabilistic distillation of coherence from pure input states, while MIO are strictly stronger. We prove a fundamental no-go result: distilling coherence from any full-rank state is impossible even probabilistically. We then present a phenomenon which prohibits any trade-off between the maximal success probability and the distillation fidelity beyond a certain threshold. Finally, we consider probabilistic distillation assisted by a catalyst and demonstrate, with specific examples, its superiority to the deterministic case.