We consider translation invariant measures on semi-infinite non-crossing random walks on the integer lattice. We classify the collective behavior of these walks under mild assumptions: they either coalesce almost surely or form bi-infinite trajectories. Bi-inifinite trajectories form measure-preserving dynamical systems, have a common asymptotic direction in 2d, and possess other nice entropic properties. Our theory also classifies the behavior of non-crossing semi-infinite geodesics in stationary first- and last-passage percolation. We also partially answer a question raised by C. Hoffman about the limiting empirical measure of weights seen by geodesics.