Early immune response to the largely used Mycobacterium bovis bacillus Calmette-Guérin (BCG) intradermal vaccine remains ill defined. Three days after BCG inoculation into the mouse ear, in addition to neutrophils infiltrating skin, we observed CD11b+ Ly-6C int Ly-6G− myeloid cells. Neutrophil depletion markedly enhanced their recruitment. These cells differed from inflammatory monocytes and required MyD88-dependent BCG-specific signals to invade skin, whereas neutrophil influx was MyD88 independent. Upon BCG phagocytosis, CD11b+ Ly-6C int Ly-6G− cells produced NO, which required the IL-1 receptor. Despite NO production, they were unable to kill BCG or the nonpathogenic Mycobacterium smegmatis. However, they markedly impaired T cell priming in the draining lymph node. Their elimination by all-trans retinoid acid treatment increased the number of IFN-γ–producing CD4 T cells. Thus, BCG vaccination recruits innate myeloid-derived suppressor cells, akin to mouse tumor-infiltrating cells. These propathogenic cells dampen the early T cell response and might facilitate BCG persistence.