Non-lymphoid tissues (NLTs) harbour a pool of adaptive immune cells, the development and phenotype of which remains largely unexplored. Here, we used single-cell RNA-seq to characterise CD4+ regulatory (Treg) and memory (Tmem) T cells in mouse skin and colon, the respective draining lymph nodes and spleen. From this data, we modelled a continuous lymphoid-to-NLT trajectory for Treg, and reconstructed the mechanisms of cell migration and NLT adaption. This revealed a shared transcriptional programme of NLT priming in both skin and colon-associated lymph nodes, followed by tissue-specific adaptation. Predicted migration kinetics were validated using a melanoma-induction model, emphasizing the relevance of key regulators and receptors, including Batf, Rora, Ccr8, Samsn1. Finally, we profiled human blood and NLT Treg and Tmem cells, identifying cross-mammalian conserved tissue signatures. In summary, we have identified molecular signals mediating NLT Treg recruitment and tissue adaptation through the combined use of computational prediction and in vivo validation.