Tissue-resident memory T cells (T_RM) persist in barrier tissues where they provide site-specific immune protection. However, the cell fate decisions and lineage pathways that lead to T_RM commitment over conventional memory T cell subsets, remains unclear. Here, we found that a distinct T_RM precursor (proT_RM) can be found in the secondary lymphoid organs early following infection. We developed a novel barcoding system where cellular division could be used as an unbiased proxy for cell fate, which allowed the permanent identification of T cells after infection based on the number of cell divisions experienced during T cell priming. Using this system, we show that proT_RM undergo relatively fewer rounds of cellular division in the skin-draining lymph node after HSV infection, and these cells preferentially give rise to T_RM in the tissue. Transcriptional profiling showed that a substantial number of T_RM core signature genes are upregulated on proT_RM early after T cell priming in the lymphoid organs, and identified markers that distinguish these cells prior to further differentiation to the T_RM phenotype in peripheral tissues. Indexed single cell RNA sequencing allowed us to determine the proT_RM transcriptional program and to establish the split between T_RM and conventional memory T cell fates. These findings provide a platform for manipulation of proT_RM cells to enhance tissue-specific protection against infectious diseases and cancers or reduce autoimmune-related disease burden.