Mathematical models of tumor-immune interactions provide an analytic framework in which to address specific questions about tumor-immune dynamics. We present a new mathematical model that describes tumor-immune interactions, focusing on the role of natural killer (NK) and CD8+ T cells in tumor surveillance, with the goal of understanding the dynamics of immune-mediated tumor rejection. The model describes tumor-immune cell interactions using a system of differential equations. The functions describing tumor-immune growth, response, and interaction rates, as well as associated variables, are developed using a least-squares method combined with a numerical differential equations solver. Parameter estimates and model validations use data from published mouse and human studies. Specifically, CD8+ T-tumor and NK-tumor lysis data from chromium release assays as well as in vivo tumor growth data are used. A variable sensitivity analysis is done on the model. The new functional forms developed show that there is a clear distinction between the dynamics of NK and CD8+ T cells. Simulations of tumor growth using different levels of immune stimulating ligands, effector cells, and tumor challenge are able to reproduce data from the published studies. A sensitivity analysis reveals that the variable to which the model is most sensitive is patient specific, and can be measured with a chromium release assay. The variable sensitivity analysis suggests that the model can predict which patients may positively respond to treatment. Computer simulations highlight the importance of CD8+ T-cell activation in cancer therapy.