We investigate the effect of ram-pressure from the intracluster medium on the stripping of H I gas in galaxies in a massive, relaxed, X-ray bright, galaxy cluster at z = 0.2 from the Blind Ultra Deep H I Environmental Survey (BUDHIES). We use cosmological simulations, and velocity versus position phase-space diagrams to infer the orbital histories of the cluster galaxies. In particular, we embed a simple analytical description of ram-pressure stripping in the simulations to identify the regions in phase-space where galaxies are more likely to have been sufficiently stripped of their H I gas to fall below the detection limit of our survey. We find a striking agreement between the model predictions and the observed location of H I-detected and non-detected blue (late-type) galaxies in phase-space, strongly implying that ram-pressure plays a key role in the gas removal from galaxies, and that this can happen during their first infall into the cluster. However, we also find a significant number of gas-poor, red (early-type) galaxies in the infall region of the cluster that cannot easily be explained with our model of ram-pressure stripping alone. We discuss different possible additional mechanisms that could be at play, including the pre-processing of galaxies in their previous environment. Our results are strengthened by the distribution of galaxy colours (optical and UV) in phase-space, that suggests that after a (gas-rich) field galaxy falls into the cluster, it will lose its gas via ram-pressure stripping, and as it settles into the cluster, its star formation will decay until it is completely quenched. Finally, this work demonstrates the utility of phase-space diagrams to analyse the physical processes driving the evolution of cluster galaxies, in particular H I gas stripping.