Highly efficient CD8⁺ T cells are associated with natural HIV control, but it has remained unclear how these cells are generated and maintained. We have used a macaque model of spontaneous SIVmac251 control to monitor the development of efficient CD8⁺ T cell responses. Our results show that SIV-specific CD8⁺ T cells emerge during primary infection in all animals. The ability of CD8⁺ T cells to suppress SIV is suboptimal in the acute phase but increases progressively in controller macaques before the establishment of sustained low-level viremia. Controller macaques develop optimal memory-like SIV-specific CD8⁺ T cells early after infection. In contrast, a persistently skewed differentiation phenotype characterizes memory SIV-specific CD8⁺ T cells in non-controller macaques. Accordingly, the phenotype of SIV-specific CD8⁺ T cells defined early after infection appears to favor the development of protective immunity in controllers, whereas SIV-specific CD8⁺ T cells in non-controllers fail to gain antiviral potency, feasibly as a consequence of early defects imprinted in the memory pool.