We show that the presence of an interaction in the quantum walk of two atoms leads to the formation of a stable compound, a molecular state. The wave function of the molecule decays exponentially in the relative position of the two atoms; hence it constitutes a true bound state. Furthermore, for a certain class of interactions, we develop an effective theory and find that the dynamics of the molecule is described by a quantum walk in its own right. We propose a setup for the experimental realization as well as sketch the possibility to observe quasi-particle effects in quantum many-body systems.