Over the course of tumor growth, cancer cells interact with normal cells via processes that are difficult to understand by experiment alone. This challenge is particularly pronounced at early stages of tumor formation, when experimental observation is most limited. Elucidating such interactions could inform both understanding of cancer and clinical practice. To address this need we developed a computational model capturing the current understanding of how individual metastatic tumor cells and immune cells sense and contribute to the tumor environment, which in turn enabled us to investigate the complex, collective behavior of these systems. Surprisingly, we discovered that tumor escape from immune control was enhanced by the existence of small differences (or heterogeneities) in the responses of individual immune cells to their environment, as well as by heterogeneities in the way that cells and the molecules they secrete are arranged in space. These conclusions held true over a range of model formulations, suggesting that this is a general feature of these tumor-immune networks. Finally, we used this model as a test bed to evaluate potential strategies for enhancing immunological control of early tumors, ultimately predicting that specifically modulating tumor-associated immune dysfunction may be more effective than simply enhanced tumor killing.