The nonpolymorphic major histocompatibility complex E (MHC-E) molecule is up-regulated on many cancer cells, thus contributing to immune evasion by engaging inhibitory NKG2A/CD94 receptors on NK cells and tumor-infiltrating T cells. To investigate whether MHC-E expression by cancer cells can be targeted for MHC-E-restricted T cell control, we immunized rhesus macaques (RM) with rhesus cytomegalovirus (RhCMV) vectors genetically programmed to elicit MHC-E-restricted CD8+ T cells and to express established tumor-associated antigens (TAAs) including prostatic acidic phosphatase (PAP), Wilms tumor-1 protein, or Mesothelin. T cell responses to all three tumor antigens were comparable to viral antigen-specific responses with respect to frequency, duration, phenotype, epitope density, and MHC restriction. Thus, CMV-vectored cancer vaccines can bypass central tolerance by eliciting T cells to noncanonical epitopes. We further demonstrate that PAP-specific, MHC-E-restricted CD8+ T cells from RhCMV/PAP-immunized RM respond to PAP-expressing HLA-E+ prostate cancer cells, suggesting that the HLA-E/NKG2A immune checkpoint can be exploited for CD8+ T cell-based immunotherapies.