Recent observations have revealed that an unexpectedly high fraction--a few per cent--of the trans-Neptunian objects (TNOs) that inhabit the Kuiper belt are binaries. The components have roughly equal masses, with very eccentric orbits that are wider than a hundred times the radius of the primary. Standard theories of binary asteroid formation tend to produce close binaries with circular orbits, so two models have been proposed to explain the unique characteristics of the TNOs. Both models, however, require extreme assumptions regarding the size distribution of the TNOs. Here we report a mechanism that is capable of producing binary TNOs with the observed properties during the early stages of their formation and growth. The only required assumption is that the TNOs were initially formed through gravitational instabilities in the protoplanetary dust disk. The basis of the mechanism is an exchange reaction in which a binary whose primary component is much more massive than the secondary interacts with a third body, whose mass is comparable to that of the primary. The low-mass secondary component is ejected and replaced by the third body in a wide but eccentric orbit.