Tuberculosis (TB) and malaria remain serious threats to global health. Bacillus Calmette-Guerin (BCG), the only licensed vaccine against TB protects against severe disseminated forms of TB in infants but shows poor efficacy against pulmonary TB in adults. Co-infections have been reported as one of the factors implicated in vaccine inefficacy. Given the geographical overlap of malaria and TB in areas where BCG vaccination is routinely administered, we hypothesized that virulence-dependent co-infection with Plasmodium species could alter the BCG-specific immune responses thus resulting in failure to protect against Mycobacterium tuberculosis. We compared virulent Plasmodium berghei and non-virulent Plasmodium chabaudi, their effects on B cells, effector and memory T cells, and the outcome on BCG-induced efficacy against M. tuberculosis infection. We demonstrate that malaria co-infection modulates both B- and T-cell immune responses but does not significantly alter the ability of the BCG vaccine to inhibit the growth of M. tuberculosis irrespective of parasite virulence. This malaria-driven immune regulation may have serious consequences in the early clinical trials of novel vaccines, which rely on vaccine-specific T-cell responses to screen novel vaccines for progression to the more costly vaccine efficacy trials.