In quantum state redistribution as introduced in [Luo and Devetak (2009)] and [Devetak and Yard (2008)], there are four systems of interest: the $A$ system held by Alice, the $B$ system held by Bob, the $C$ system that is to be transmitted from Alice to Bob, and the $R$ system that holds a purification of the state in the $ABC$ registers. We give upper and lower bounds on the amount of quantum communication and entanglement required to perform the task of quantum state redistribution in a one-shot setting. Our bounds are in terms of the smooth conditional min- and max-entropy, and the smooth max-information. The protocol for the upper bound has a clear structure, building on the work [Oppenheim (2008)]: it decomposes the quantum state redistribution task into two simpler quantum state merging tasks by introducing a coherent relay. In the independent and identical (iid) asymptotic limit our bounds for the quantum communication cost converge to the quantum conditional mutual information $I(C:R|B)$, and our bounds for the total cost converge to the conditional entropy $H(C|B)$. This yields an alternative proof of optimality of these rates for quantum state redistribution in the iid asymptotic limit. In particular, we obtain a strong converse for quantum state redistribution, which even holds when allowing for feedback.