About 20% of all massive stars in the Milky Way have unusually high velocities, the origin of which has puzzled astronomers for half a century. We argue that these velocities originate from strong gravitational interactions between single stars and binaries in the centers of star clusters. The ejecting binary forms naturally during the collapse of a young (less than or similar to 1 milion years old) star cluster. This model replicates the key characteristics of OB runaways in our galaxy, and it explains the presence of runaway stars of greater than or similar to 100 solar masses (M-circle dot) around young star clusters, such as R136 and Westerlund 2. The high proportion and the distributions in mass and velocity of runaways in the Milky Way are reproduced if the majority of massive stars are born in dense and relatively low-mass (5000 to 10,000 M-circle dot) clusters.