We use simple mathematical models to examine the dynamics of primary and secondary cytotoxic T-lymphocyte (CTL) responses to viral infections. In particular, we are interested in conditions required to resolve the infection and to protect the host upon secondary challenge. While protection against reinfection is only effective in a restricted set of circumstances, we find that resolution of the primary infection requires persistence of CTL precursors (GTLp), as well as a fast rate of activation of the CTLp. Since these are commonly the defining characteristics of CTL memory, we propose that CTL memory may have evolved in order to clear the virus during primary challenge. We show experimental data from lymphocytic choriomeningitis virus infection in mice, supporting our theory on CTL memory. We adapt our models to HIV and find that immune impairment during the primary phase of the infection may result in the failure to establish CTL memory which in turn leads to viral persistence. Based on our models we suggest conceptual treatment regimes which ensure establishment of CTL memory. This would allow the immune response to control HIV in the long term in the absence of continued therapy.