During trafficking through tissues, T cells fine-tune their motility to balance the extent and duration of cell-surface contacts with the need to traverse an entire organ. In vivo, Myosin-IIA-deficient T cells exhibited a triad of defects including over-adherence to high-endothelial venules, reduced interstitial migration, and inefficient completion of recirculation through lymph nodes. Spatiotemporal analysis of 3-dimensional motility in microchannels revealed that the degree of confinement and Myosin-IIA function, rather than integrin adhesion as proposed by the haptokinetic model, optimize motility rate. This occurs via a Myosin-IIA-dependent rapid ‘walking’ motility mode using multiple small and simultaneous adhesions to the substrate, which prevent spurious and prolonged adhesions. Adhesion discrimination provided by Myosin-IIA is thus necessary for optimizing motility through complex tissues.