While regulatory T (Treg) cells are traditionally viewed as professional suppressors of antigen-presenting and effector T cells in both autoimmunity and cancer, recent findings of distinct Treg functions in tissue maintenance suggest that their regulatory purview extends to a wider range of cells and is broader than previously assumed. To elucidate tumoral Treg “connectivity” to diverse tumor-supporting accessory cell types, we explored immediate early changes in their single cell transcriptomes upon punctual Treg depletion in experimental lung cancer and injury-induced inflammation. Prior to any notable T cell activation and inflammation, fibroblasts, endothelial and myeloid cells exhibited pronounced changes in their gene expression in both cancer and injury settings. Factor analysis revealed shared Treg-dependent gene programs, also recapitulated in-situ, assayed by spatial transcriptomics of the same experimental setting. Of the shared pathways we focused foremost on prominent upregulation of VEGF signaling-related genes ensuing Treg deprivation in either setting, as well as in Treg-poor vs Treg-rich human lung adenocarcinomas. Accordingly, punctual Treg depletion combined with short-term VEGF blockade showed markedly improved control of PD-1 blockade-resistant lung adenocarcinoma progression in mice compared to the corresponding monotherapies, highlighting a promising factor-based querying approach to elucidating novel rational combination treatments of solid organ cancers.