HIV is primarily a sexually transmitted virus, entering through the mucosal surfaces prior to systemically invading the host. Therefore, induction of potent mucosal immunity with the capacity to prevent infection and viral propagation at the site of entry will be required for an efficacious HIV/AIDS vaccine. In addition, results from preclinical and clinical HIV vaccine candidates suggest that neither CD8+T cell nor antibody responses alone can prevent HIV infection. We are currently developing a novel prime/boost regimen that combines a BCG vector for priming and replicating vaccinia virus (m8∆) for boost. Both BCG and vaccinia vectors are widely used in Japan as vaccine for tuberculosis and small pox.