Trained immunity (TI) is the process wherein innate immune cells gain functional memory upon exposure to specific ligands or pathogens, leading to augmented inflammatory responses and pathogen clearance upon secondary exposure. While the differentiation of hematopoietic stem cells (HSCs) and reprogramming of bone marrow (BM) progenitors are well-established mechanisms underpinning durable TI protection, remodeling of the cellular architecture within the tissue during TI remains underexplored. Here, we study the effects of peritoneal Bacillus Calmette-Guerin (BCG) administration to find TI-mediated protection in the spleen against a subsequent heterologous infection by the Gram-negative pathogen Salmonella Typhimurium (S.Tm). Utilizing single cell RNA-sequencing and flow cytometry, we discerned STAT1-regulated genes in TI-associated resident and recruited splenic myeloid populations. The temporal dynamics of TI were further elucidated, revealing both early and delayed myeloid subsets with time-dependent, cell type-specific STAT1 signatures. Using lineage tracing, we find that tissue-resident red pulp macrophages (RPM), initially depleted by BCG exposure, are restored from both tissue-trained, self-renewing macrophages and from bone marrow-derived progenitors, fostering long lasting local defense. Early inhibition of STAT1 activation, using specific JAK-STAT inhibitors, reduces both RPM loss and recruitment of trained monocytes. Our study suggests a temporal window soon after BCG vaccination, in which STAT1-dependent activation of long-lived resident cells in the tissue mediates localized protection.