Brain tumors are among the deadliest malignancies. The brain tumor microenvironment (TME) hosts a unique collection of cells, soluble factors, and extracellular matrix components that regulate disease evolution of both primary and metastatic brain malignancies. It is established that macrophages and other myeloid cells are abundant in the brain TME and strongly correlate with aggressive phenotypes and distinct genetic signatures, while lymphoid cells are less frequent but are now known to have a pronounced effect on disease progression. Different types of brain tumors vary widely in their microenvironmental contexture, and the proportion of various stromal components impacts tumor biology. Indeed, emerging evidence suggests an intimate link between the molecular signature of tumor cells and the composition of the TME, shedding light on the mechanisms which underlie microenvironmental heterogeneity in brain cancer. In this review, we discuss the association between TME composition and the diverse molecular profiles of primary gliomas and brain metastases. We also discuss the implications of these associations on the efficacy of immunotherapy in brain malignancies. An appreciation for the causes and functional consequences of microenvironmental heterogeneity in brain cancer will be of crucial importance to the rational design of microenvironment-targeted therapies for these deadly diseases.