Biophysical mechanisms underlying collective cell migration of eukaryotic cells have been studied extensively in recent years. One mechanism that induces cells to correlate their motions is contact inhibition of locomotion, by which cells migrating away from the contact site. Here, we report that tail-following behavior at the contact site, termed contact following locomotion (CFL), can induce a non-trivial collective behavior in migrating cells. We show the emergence of a traveling band showing polar order in a mutant Dictyostelium cell that lacks chemotactic activity. We find that CFL is the cell-cell interaction underlying this phenomenon, enabling a theoretical description of how this traveling band forms. We further show that the polar order phase consists of subpopulations that exhibit characteristic transversal motions with respect to the direction of band propagation. These findings describe a novel mechanism of collective cell migration involving cell-cell interactions capable of inducing traveling band with polar order.