We experimentally and theoretically study phase coherence in two-component Bose-Einstein condensates of $^{87}{rm Rb}$ atoms on an atom chip. Using Ramsey interferometry we measure the temporal decay of coherence between the $|F=1,m_{F}=-1rangle$ and $|F=2,m_{F}=+1rangle$ hyperfine ground states. We observe that the coherence is limited by random collisional phase shifts due to the stochastic nature of atom loss. The mechanism is confirmed quantitatively by a quantum trajectory method based on a master equation which takes into account collisional interactions, atom number fluctuations, and losses in the system. This decoherence process can be slowed down by reducing the density of the condensate. Our findings are relevant for experiments on quantum metrology and many-particle entanglement with Bose-Einstein condensates and the development of chip-based atomic clocks.