Tumor growth involves a dynamic interplay between cancer cells and host cells, which collectively form a tumor microenvironmental network that either suppresses or promotes tumor growth under different conditions. The transition from tumor suppression to tumor promotion is mediated by a tumor-induced shift in the local immune state, and despite the clinical challenge this shift poses, little is known about how such dysfunctional immune states are initiated. Clinical and experimental observations have indicated that differences in both the composition and spatial distribution of different cell types and/or signaling molecules within the tumor microenvironment can strongly impact tumor pathogenesis and ultimately patient prognosis. How such “functional” and “spatial” heterogeneities confer such effects, however, is not known. To investigate these phenomena at a level currently inaccessible by direct observation, we developed a computational model of a nascent metastatic tumor capturing salient features of known tumor-immune interactions that faithfully recapitulates key features of existing experimental observations. Surprisingly, over a wide range of model formulations, we observed that heterogeneity in both spatial organization and cell phenotype drove the emergence of immunosuppressive network states. We determined that this observation is general and robust to parameter choice by developing a systems-level sensitivity analysis technique, and we extended this analysis to generate other parameter-independent, experimentally testable hypotheses. Lastly, we leveraged this model as an in silico test bed to evaluate potential strategies for engineering cell-based therapies to overcome tumor associated immune dysfunction and thereby identified modes of immune modulation predicted to be most effective. Collectively, this work establishes a new integrated framework for investigating and modulating tumor-immune networks and provides insights into how such interactions may shape early stages of tumor formation.