It is well established that tissue macrophages and tissue-resident memory CD8+ T cells (TRM) play important roles for pathogen sensing and rapid protection of barrier tissues. In contrast, the mechanisms by which these two cell types cooperate for homeostatic organ surveillance after clearance of infections is poorly understood. Here, we used intravital imaging to show that TRM dynamically followed tissue macrophage topology in noninflamed murine submandibular salivary glands (SMGs). Depletion of tissue macrophages interfered with SMG TRM motility and caused a reduction of interepithelial T cell crossing. In the absence of macrophages, SMG TRM failed to cluster in response to local inflammatory chemokines. A detailed analysis of the SMG microarchitecture uncovered discontinuous attachment of tissue macrophages to neighboring epithelial cells, with occasional macrophage protrusions bridging adjacent acini and ducts. When dissecting the molecular mechanisms that drive homeostatic SMG TRM motility, we found that these cells exhibit a wide range of migration modes: In addition to chemokine- and adhesion receptor-driven motility, resting SMG TRM displayed a remarkable capacity for autonomous motility in the absence of chemoattractants and adhesive ligands. Autonomous SMG TRM motility was mediated by friction and insertion of protrusions into gaps offered by the surrounding microenvironment. In sum, SMG TRM display a unique continuum of migration modes, which are supported in vivo by tissue macrophages to allow homeostatic patrolling of the complex SMG architecture.