Immune tolerance to tumor-associated self-antigens poses a major challenge in the ability to mount an effective cancer vaccine response. To overcome immune tolerance to HER-2, we formulated DNA vaccines that express both human HER-2 and heterologous rat Neu sequences in separate plasmids or as single hybrid constructs that encode HER-2/Neu fusion proteins. Candidate vaccines were tested in Her-2 transgenic (Tg) mice of BALB/c (BALB), BALB/cxC57BL/6 F1 (F1), or C57BL/6 (B6) background, which exhibit decreasing immune responsiveness to HER-2. Analysis of various cocktails or hybrid vaccines defined a requirement for particular combination of HER/2/Neu sequences to effectively prime immune effector cells in HER-2 Tg mice. In B6 HER-2 Tg mice, rejection of HER-2-positive tumors protected mice from HER-2-negative tumors, providing evidence of epitope spreading. Our findings show that a strategy of combining heterologous antigen with self-antigens could produce a potent DNA vaccine that may be applicable to other tumor-associated antigens.