The need for an affordable, safe and effective HIV vaccine has never been greater. As the immunogenicity of all the vaccine vectors being evaluated currently in human populations is limited, novel vaccine strategies are needed to stimulate the innate immune system, to generate high levels of neutralizing antibodies and to induce strong cell-mediated and mucosal immunity. There is strong evidence for a role for cytotoxic T lymphocytes in the containment of HIV replication. Several vaccine approaches have been tested to elicit anti-HIV cytotoxic T-lymphocyte responses. One promising approach is Bacillus Calmette-Guérin (BCG) as a bacterial live recombinant vaccine vehicle. BCG has a long record of safety in humans and is able to induce long-lasting immunity. In this review, we describe the limitations and challenges of developing a recombinant BCG-based HIV vaccine. We also emphasize possible approaches for overcoming the plasmid instability in vivo and the low levels of gene expression and immunogenicity induction. Today, projects all over the world are focused on the development of an AIDS vaccine. Overcoming the remaining scientific, logistical and financial hurdles to the development of an effective HIV vaccine will require real imagination and firm commitment from all stakeholders.