Reliable and effective induction of cytotoxic T-lymphocytes (CTL) is one of the prime objectives of vaccine research. Previously, novel HIV vaccine candidates were constructed as a string of CTL epitopes (20 human, 3 macaque and 1 mouse) delivered using a DNA vector [Hanke T, Schneider J, Gilbert SG, Hill AVS, McMichael A. DNA multi-CTL epitope vaccines for HIV and Plasmodium falciparum: immunogenicity in mice. Vaccine 1998;16:426-435.] or modified vaccinia Ankara (MVA [Hanke T, Blanchard TJ, Schneider J, Ogg GS, Tan R, Becker MSC, Gilbert SG, Hill AVS, Smith GL, McMichael A. Immunogenicities of intravenous and intramuscular administrations of MVA-based multi-CTL epitope vaccine for HIV in mice. J Gen Virol 1998;79:83-90.]), i.e. vaccine vehicles acceptable for use in humans. In mice, a single intramuscular (i.m.) needle injection of either vaccine alone elicited good CTL responses. Here, it is demonstrated that the multi-epitope DNA also induced CTL when delivered intradermally using the Accell gene gun. The CTL responses increased after re-immunization and after three deliveries were comparable to those induced by a single i.m. injection. Recent evidence indicates that combining routes and vaccine vehicles enhances the immunogenicity of vaccine-delivered or -encoded antigens. Here, it is shown that administration of DNA by an i.m. priming/gene gun boosting more efficiently induced CTL than gene gun priming/i.m. boosting. A similar increment was obtained by sequential vaccinations using a gene gun-delivered DNA followed by recombinant MVA. Thus particular sequences of routes or vaccine vehicles rather than simple prime-boost delivery of a single vaccine is critical for an effective elicitation of CTL.