Abstract Staying to exploit remaining resources or leaving to seek better options elsewhere is a fundamental decision across species. Optimal patch foraging theories propose deterministic rules for when to leave a depleting resource but real foragers show considerable variability in when they leave. Decisions between simultaneously-presented options are often assumed to follow a stochastic decision policy, adding randomness into the choice process to allow for exploration of potentially better alternatives. Whether a stochastic choice policy can account for variability in sequential foraging decisions, and what predictions such a policy makes for the mechanisms of foraging choice, are unknown. Here using patch foraging datasets in both humans ( n = 39, n = 29) and rats ( n = 8), we show that foragers making a stochastic choice of when to leave a patch is sufficient to explain their variability. We also show stochastic choice makes two unintuitive predictions, which we validate in our data. First, under a wide range of conditions, stochastic choice makes foragers’ leaving variability independent of the rewards available in the environment. Second, that foragers use a suboptimal internal function for setting their choice stochasticity from their environment’s average reward rate. Our findings suggest stochastic choice is an underappreciated but powerful contributor to foraging decisions, and highlight how behavioural variability, which is often overlooked, can reveal the algorithmic underpinning of decisions.