Granzyme B (GrB) is a well-characterised protease, best known for its role in targeted destruction of infected or neoplastic cells by cytotoxic lymphocytes (CLs). GrB also exerts other activities, such as cleavage of extracellular matrix (ECM) components (e.g. fibronectin and laminin). Nevertheless, whether GrB is involved in the migration of CL in vivo is currently unknown. Our results show that GrB-deficient CL, including effector T cells and NK cells, exhibit impaired homing to inflamed tissues. Using in vitro invasion and migration assays, we demonstrate that GrB is constitutively secreted from migrating CLs and enables chemokine-driven CL movement through basement membranes (BM). Proteomic analysis identified several BM constituents as targets of the enzymatic activity of GrB. Intravital multi-photon imaging of effector T cells in inflamed cremaster muscle venules revealed that GrB deficient cells could adhere to the vessel wall, but were impaired in diapedesis. Our results highlight an unexpected function of GrB in CL transmigration through the vascular wall in vivo via BM remodeling.