For a mobile spin-1/2 impurity, coupled antiferromagnetically to a one-dimensional gas of fermions, perturbative ideas have been used to argue in favor of two-channel Kondo behavior of the impurity spin. Here we combine general considerations and extensive numerical simulations to show that the problem displays a novel quantum phase transition between two-channel and one-channel Kondo screening upon increasing the Kondo coupling. We construct a ground-state phase diagram and discuss the various nontrivial crossovers as well as possible experimental realizations.