To fulfill their killing functions, cytotoxic T lymphocytes (CTLs) need to migrate to search for their target cells in complex biological microenvironments, a key component of which is extracellular matrix (ECM). The mechanisms underlying CTLs navigation are not well understood so far. Here we use a collagen assay as a model for the ECM and analyze the migration trajectories of primary human CTLs in collagen matrices with different concentrations. We observe different migration patterns for individual T cells. Three different motility types can be distinguished: slow, fast and mixed motilities. Slow CTLs remain nearly stationary within the collagen matrix and show slightly anti-persistent motility, while the fast ones move quickly and persistent (i.e. with not too large turning angles). The dynamics of the mixed type consists of periods of slow and fast motions; both states are persistent, but they have different persistencies. The dynamics can be well described by a two-state persistent random walk model. We extract the parameters of the model by analyzing experimental data. The mean square displacements predicted by the model and those measured experimentally are in very good agreement, without any fitting parameter. Potential reasons for the observed two-state motility are discussed. T cells dig the collagen during their migration and form channels, which facilitate the movement of other CTLs in the collagen network.