The induction of IFN-gamma-secreting CD8+ T cells and neutralizing antibodies to HIV-1 are both key requirements for prevention of viral transmission and clearance of pathogenic HIV. Although DNA vaccination has been shown to induce both humoral and cellular immune responses against HIV antigens, the magnitude of the immune responses has always been disappointing. In this report, we analyze the ability of polyethylenimine (PEI)-DNA complex expressing an HIV-glycoprotein 120 (gp120) antigen (PEI-pgp120) to induce systemic CD8+ T cell and humoral responses to the gp120 antigen. The administration of PEI-plasmid complex resulted in rapid elevation of serum levels of IL-12 and IFN-gamma. Furthermore, a single administration of PEI-pgp120 complex elicits a number of gp120-specific CD8+ T cells 20 times higher than that elicited by three intramuscular injections of naked DNA. Interestingly, we found that systemic vaccination with PEI-pgp120 induced protective immune responses against both systemic and mucosal challenges with a recombinant vaccinia virus expressing a gp120 antigen. The data also demonstrated that the depletion of macrophages with liposome-encapsulated clodronate completely abolished gp120-specific cellular response. Overall, our results showed that a single administration of PEI-pgp120 complexes, eliciting strong immune responses, is an effective vaccination approach to generate protection against systemic and mucosal viral infections.