The failure of current BCG vaccine in controlling the global tuberculosis (TB) epidemic highlights an urgent need for improved TB vaccine formulations. In this study, we have investigated the effect of a novel adenoviral granulocyte macrophage-colony stimulating factor (GM-CSF) transgene-based adjuvant formulation (AdGM-CSF) on BCG vaccination in a mouse strain that is genetically weak responders to BCG vaccine. BALB/c mice were immunized subcutaneously (s.c.) with PBS, BCG, or BCG plus AdGM-CSF or control vector Addl70-3, the immunogenicity of BCG vaccine was evaluated by type 1 IFN-gamma production from lymphocytes of various lymphoid tissues upon mycobacterial antigen stimulation ex vivo. While mycobacterial antigen-specific IFN-gamma production was slightly enhanced by co-immunization BCG with Addl70-3 as compared to BCG immunization alone, a marked increase both in the magnitude and longevity of anti-mycobacterial type 1 immunity was observed in the local draining lymph nodes and spleens by immunization with AdGM-CSF-adjuvanted BCG. Furthermore, there was a significant increase in the number of mycobacterial antigen-specific IFN-gamma releasing CD4 T cells in mice immunized with AdGM-CSF-adjuvanted BCG vaccine. Consistent with these enhanced T-cell immunity and memory responses, AdGM-CSF-adjuvanted BCG vaccine significantly improved immune protection against secondary mycobacterial challenge. Our results suggest that GM-CSF transgene-based adjuvant formulation is an effective way to improve the immunogenicity of BCG vaccine.