Vaccines that elicit protective cytotoxic T lymphocytes (CTL) may improve on or augment those designed primarily to elicit antibody responses. However, we have little basis for estimating the numbers of CTL required for sterilising immunity at an infection site. To address this we begin with a theoretical estimate obtained from measurements of CTL surveillance rates and the growth rate of a virus. We show how this estimate needs to be modified to account for (i) the dynamics of CTL-infected cell conjugates, and (ii) features of the virus lifecycle in infected cells. We show that provided the inoculum size of the virus is low, the dynamics of CTL-infected cell conjugates can be ignored, but knowledge of virus life-histories is required for estimating critical thresholds of CTL densities. We show that accounting for virus replication strategies increases estimates of the minimum density of CTL required for immunity over those obtained with the canonical model of virus dynamics, and demonstrate that this modeling framework allows us to predict and compare the ability of CTL to control viruses with different life history strategies. As an example we predict that lytic viruses are more difficult to control than budding viruses when net reproduction rates and infected cell lifetimes are controlled for. Further, we use data from acute SIV infection in rhesus macaques to calculate a lower bound on the density of CTL that a vaccine must generate to control infection at the entry site. We propose that critical CTL densities can be better estimated either using quantitative models incorporating virus life histories or with in vivo assays using virus-infected cells rather than peptide-pulsed targets.