The causative agent of Plague, Yersinia pestis, is a highly virulent pathogen and a potential bioweapon. Depending on the route of infection, two prevalent occurrences of the disease are known, bubonic and pneumonic. The latter has a high fatality rate. In the absence of a licensed vaccine, intense efforts to develop a safe and efficacious vaccine have been conducted, and humoral-driven subunit vaccines containing the F1 and LcrV antigens are currently under clinical trials. It is well known that a cellular immune response might have an essential additive value to immunity and protection against Y. pestis infection. Nevertheless, very few documented epitopes eliciting a protective T-cell response have been reported. Here, we present a combined high throughput computational and experimental effort towards identification of CD8 T-cell epitopes. All 4067 proteins of Y. pestis were analyzed with state-of-the-art recently developed prediction algorithms aimed at mapping potential MHC class I binders. A compilation of the results obtained from several prediction methods revealed a total of 238,000 peptide candidates, which necessitated downstream filtering criteria. Our previously established and proven approach for enrichment of true positive CTL epitopes, which relies on mapping clusters rich in tandem or overlapping predicted MHC binders ("hotspots"), was applied, as well as considerations of predicted binding affinity. A total of 1532 peptides were tested for their ability to elicit a specific T-cell response by following the production of IFNγ from splenocytes isolated from vaccinated mice. Altogether, the screen resulted in 178 positive responders (11.8%), all novel Y. pestis CTL epitopes. These epitopes span 113 Y. pestis proteins. Substantial enrichment of membrane-associated proteins was detected for epitopes selected from hotspots of predicted MHC binders. These results considerably expand the repertoire of known CTL epitopes in Y. pestis and pave the way to attest their protective potential, and hence their contribution to a future potent subunit vaccine.