Although its potential for vaccine development is already known, the introduction of recombinant human immunodeficiency virus (HIV) genes to Mycobacterium bovis bacille Calmette-Guérin (BCG) has thus far elicited only limited responses. In order to improve the expression levels, we optimized the codon usage of the HIV type 1 (HIV-1) p24 antigen gene of gag (p24 gag) and established a codon-optimized recombinant BCG (rBCG)-p24 Gag which expressed a 40-fold-higher level of p24 Gag than did that of nonoptimized rBCG-p24 Gag. Inoculation of mice with the codon-optimized rBCG-p24 Gag elicited effective immunity, as evidenced by virus-specific lymphocyte proliferation, gamma interferon ELISPOT cell induction, and antibody production. In contrast, inoculation of animals with the nonoptimized rBCG-p24 Gag induced only low levels of immune responses. Furthermore, a dose as small as 0.01 mg of the codon-optimized rBCG per animal proved capable of eliciting immune responses, suggesting that even low doses of a codon-optimized rBCG-based vaccine could effectively elicit HIV-1-specific immune responses.