CD8$^+$ cytotoxic T lymphocytes (CTLs) are critical for protection against intracellular pathogens but often have been difficult to induce by subunit vaccines in animals. DNA vaccines elicit protective CD8$^+$ T cell responses. Malaria-naïve volunteers who were vaccinated with plasmid DNA encoding a malaria protein developed antigen-specific, genetically restricted, CD8$^+$ T cell-dependent CTLs. Responses were directed against all 10 peptides tested and were restricted by six human lymphocyte antigen (HLA) class I alleles. This first demonstration in healthy naive humans of the induction of CD8$^+$ CTLs by DNA vaccines, including CTLs that were restricted by multiple HLA alleles in the same individual, provides a foundation for further human testing of this potentially revolutionary vaccine technology.