The cellular actin cortex is the cytoskeletal structure primarily responsible for the control of animal cell shape and as such plays a central role in cell migration. In T-cell mediated immune responses to cancers, and in burgeoning adoptive transfer immunotherapies, cytotoxic T lymphocytes need to navigate various barriers and organs to reach the tumour and then effectively find and engage their targets. This tissue-invasive cell migration relies on polarised shape changes and forces mediated by the actomyosin cortex, which manifest in different cellular protrusions such as lamellipodia, filopodia and blebs, whose functional significance remain incompletely understood. We have developed a novel image analysis platform capable of automatically detecting and classifying the protrusions that cells extend during locomotion, and delivering advanced morphological and kinetic measurements. We show that by selectively inhibiting various components of the actomyosin machinery, primary T cells can be forced to adopt differing migration modes and extend unique sets of protrusions. By analysing T cell movement in 3-dimensional matrices embedded with tumour cells, we can systematically uncover the contribution of various actin-binding proteins to the scanning process and migration efficacy in complex environments. We show that actin nucleators control overall migration dynamics that result in differing directedness and search volume coverage, and that their precise orchestration thus plays an instrumental role in efficiently locating and rejecting target cells.