The von Neumann entropy is a key quantity in quantum information theory and, roughly speaking, quantifies the amount of quantum information contained in a state when many identical and independent i.i.d. copies of the state are available, in a regime that is often referred to as being asymptotic. In this work, we provide a new operational characterization of the von Neumann entropy which neither requires an i.i.d. limit nor any explicit randomness. We do so by showing that the von Neumann entropy fully characterizes single-shot state transitions in unitary quantum mechanics, as long as one has access to a catalyst - an ancillary system that can be re-used after the transition - and an environment which has the effect of dephasing in a preferred basis. Building upon these insights, we formulate and provide evidence for the catalytic entropy conjecture, which states that the above result holds true even in the absence of decoherence. If true, this would prove an intimate connection between single-shot state transitions in unitary quantum mechanics and the von Neumann entropy. Our results add significant support to recent insights that, contrary to common wisdom, the standard von Neumann entropy also characterizes single-shot situations and opens up the possibility for operational single-shot interpretations of other standard entropic quantities. In new work in press in the Physical Review Letters we discuss implications of these insights to readings of the third law of quantum thermodynamics and hint at potentially profound implications to holography.