Realizing robust quantum phenomena in strongly interacting systems is one of the central challenges in modern physical science. Approaches ranging from topological protection to quantum error correction are currently being explored across many different experimental platforms, including electrons in condensed-matter systems', trapped atoms' and photons'. Although photon-photon interactions are typically negligible in conventional optical media, strong interactions between individual photons have recently been engineered in several systems(4-10). Here, using coherent coupling between light and Rydberg excitations in an ultracold atomic gas, we demonstrate a controlled and coherent exchange collision between two photons that is accompanied by a pi/2 phase shift. The effect is robust in that the value of the phase shift is determined by the interaction symmetry rather than the precise experimental parameters(7,10-13), and in that it occurs under conditions where photon absorption is minimal. The measured phase shift of 0.48(3)pi is in excellent agreement with a theoretical model. These observations open a route to realizing robust single-photon switches and all-optical quantum logic gates, and to exploring novel quantum many-body phenomena with strongly interacting photons.