CD8+ cytotoxic T lymphocytes (CTL) and natural killer (NK) cells are the main cytotoxic killer cells of the human body to eliminate pathogen-infected or tumorigenic cells (= target cells). To find their targets they have to navigate and migrate through a complex biological microenvironments, a key component of which is the extracellular matrix (ECM). The mechanisms underlying killer cell’s navigation are not well understood. To mimic an ECM we use a matrix formed by different collagen concentrations, and analyze migration trajectories of primary human CTLs. Different migration patterns are observed and can be grouped into three motility types: slow, fast and mixed. The dynamics are well described by a two-state persistent random walk model which allows cells to switch between slow motion with low persistence, and fast motion with high persistence. We hypothesize that the slow motility mode describes CTLs creating channels through the collagen matrix by deforming and tearing apart collagen fibers, and that the fast motility mode describes CTLs moving within these channels. Experimental evidence supporting this scenario is presented by visualizing migrating T cells following each other on exactly the same track and showing cells moving quickly in channel-like cavities within the surrounding collagen matrix. Consequently, the efficiency of the stochastic search process of CTLs in the ECM should strongly be influenced by a dynamically changing channel network produced by the killer cells themselves.