All communities may re-assemble after disturbance. Predictions for re-assembly outcomes are, however, rare. Here we model how fish communities in an extremely variable Australian desert river re-assemble following episodic floods and drying. We apply information entropy to quantify variability in re-assembly and the dichotomy between stochastic and deterministic community states. Species traits were the prime driver of community state: poor oxygen tolerance, low dispersal ability, and high fecundity constrain variation in re-assembly, shifting assemblages towards more stochastic states. In contrast, greater connectivity, while less influential than the measured traits, results in more deterministic states. Ecology has long recognised both the stochastic nature of some re-assembly trajectories and the role of evolutionary and bio-geographic processes. Our models explicitly test the addition of species traits and landscape linkages to improve predictions of community re-assembly, and will be useful in a range of different ecosystems.