The function of most immune cells depends on their ability to migrate through complex microenvironments, either randomly to patrol for the presence of antigens or directionally to reach their next site of action. The actin cytoskeleton and its partners are key conductors of immune cell migration as they control the intrinsic migratory properties of leukocytes as well as their capacity to respond to cues present in their environment. In this review we focus on the latest discoveries regarding the role of the actomyosin cytoskeleton in optimizing immune cell migration in complex environments, with a special focus on recent insights provided by physical modeling.