Migration of leukocytes is essential for the induction, maintenance, and regulation of immune responses. On their trafficking routes, leukocytes encounter microenvironments of diverse mechanochemical composition, such as epithelial sheets, fibrillar networks, and cell-dense lymphatic organs. These microenvironments impose fundamental challenges on leukocytes, which include adhesive crawling under high shear stress, extreme cellular deformation while crossing physical barriers, and pathfinding in maze-like 3D environments. Crossing these microenvironments in a fast and efficient manner is a hallmark of leukocyte biology. We review the underlying cell biological principles and molecular mechanisms. By integrating knowledge from physiological in vivo and reductionistic in vitro approaches, we developed a holistic view of leukocyte migration strategies, including misregulation in disease and mechanistic hijacking by tumor cells.