Background: Tumor-infiltrating lymphocytes (TILs) and tumor-associated macrophages (TAMs) have increasingly been reported to impact the brain metastatic process of solid tumors. However, data on intra-individual differences between primary tumor and brain metastasis (BM), as well as their correlation with clinical outcome parameters, is scarce. Methods: We retrospectively identified patients who received resection of the primary tumor and BM between 01/1990 and 10/2022. Density quantification of TAMs (CD68⁺, CD163⁺) and TILs (CD3⁺, CD8⁺, CD45RO⁺, FOXP3⁺) was performed by immunohistochemical staining of matched tumor tissue samples. Images were processed with QuPath software and heterogeneity of generated heatmaps was measured by Shannon Entropy. Time-to-BM (TTBM) was defined as the time from diagnosis of the primary tumor until the first diagnosis of BM. Results: In total, 104 patients (46.2% female; median age 57.3 years at BM diagnosis) were included: 78/104 (75%) non-small cell lung cancer, 18/104 (17%) breast cancer, 8/104 (8%) renal cell carcinomas. Densities of CD3⁺ (p < 0.001) and CD8⁺-TILs (p < 0.001) were higher in primary tumor samples, while CD68⁺ (p = 0.035) and CD163⁺-TAM densities (p < 0.001) were higher in the matched BM. Higher CD3⁺, CD8⁺-TILs and CD163⁺-TAMs densities in primary tumors were associated with shorter TTBM (p = 0.005, p = 0.015 and p = 0.006, respectively). Higher entropies of CD3⁺ (p < 0.001) and FOXP3⁺ (p = 0.011) TILs were observed in primary tumors compared to BM. Longer TTBM was associated with higher entropy of FOXP3⁺ TILs (p = 0.024) and lower entropy in CD163⁺ TAMs (p = 0.039). No significant associations of immune cell densities or entropies with OS after BM diagnosis were found. Discussion: By utilizing a unique cohort of matched primary tumor and BM tissue samples, we could demonstrate higher TIL densities in primary tumors and higher TAM densities in BM, respectively. Higher cell densities of CD3⁺, CD8⁺-TILs and CD163⁺-TAMs in primary tumors were associated with shorter TTBM, while a larger difference between CD3⁺ and CD8⁺ densities between primary tumor and BM was associated with longer TTBM. These findings highlight the potential of targeting TAMs as a therapeutic strategy to mitigate the development of brain metastases.