The catalytic hydrogenation of olefins promoted by transition metals, represented here by the conversion of ethylene with platinum, was studied under a unique regime representing pressures in the mTorr range and single-collision conditions. Isotope labeling was used to follow the concurrent H-D exchange steps that occur during this conversion. Multiple isotope substitutions were observed in the resulting ethane products, reflecting the operability of the reversible stepwise mechanism proposed a long time ago by Horiuti and Polanyi. In fact, the ethane isotopologue distributions obtained in these experiments reflect a much higher probability for the dehydrogenation of ethyl intermediates back to the olefin, relative to the hydrogenation to ethane, than typically seen in this catalysis. In addition, a second mechanistic pathway was clearly identified, responsible for most of the dideuteroethane produced. Based on the dependence of the rates of formation of each isotopologue on the fluxes of deuterium and ethylene, it is argued that this second route may be a "reverse" Eley-Rideal step between gas-phase ethylene and two deuterium atoms adsorbed on adjacent sites of the platinum surface. The clear identification of this second pathway is new, and was possible thanks to our ability to explore a new single-collision intermediate pressure regime.