Increased appreciation of intraclonal heterogeneity of tumors in the past decade has led to the resurgence of the cancer stem cell hypothesis. This hypothesis also has potential implications for immunologic approaches targeting cancer, and it has been suggested that vaccines targeting cancer stem cells may be essential for durable antitumor immunity. Recent studies have provided novel insights into the nature of antigenic targets expressed on putative cancer stem cells and the capacity of both the innate and the adaptive immune system to target these cells, as well as the associated challenges. While the phenotypic properties of cancer stem cells may be plastic, their stemness and capacity for self-renewal may depend on a limited set of genes. Several of these genes overlap with those regulating stemness in embryonal stem cells and are also emerging as potential oncogenes in some cancers. Immunologic approaches targeting stemness-associated pathways in cancer may provide an important strategy for the prevention of diverse cancers, including those occurring in the context of regenerative therapies.