There is currently a need to develop safe and effective vaccines for the induction of cellular, in particular cytotoxic T-lymphocyte-mediated, protective immune responses. This review focuses on the challenges presented by such an endeavor, current strategies for the induction of such responses, and the relatively new idea that recombinant yeast may represent an ideal vaccine vector for the induction of cellular immune responses.