Lung infection by Mycobacterium tuberculosisis characterised by chronic infection of lung-resident macrophages, long considered to be the primary hosts and determinants of the outcome of the early immune response. Although alveolar macrophages are well-known to host intracellular mycobacteria at later stages of disease, little is known about the earliest events of the innate immune response. The phagocytes that take up mycobacteria immediately following infection, and how the early lung phagocyte response is altered by vaccination with Mycobacterium bovis bacille Calmette-Guérin (BCG) were unknown. Using BCG expressing the bright red fluorescent protein tdTomato and flow cytometry, we modelled early infection in C57BL/6 mice and tracked phagocyte population kinetics and uptake of mycobacteria, to better understand the involvement of specific phagocyte subsets. By 1 day post-infection, dose-dependent accumulation of neutrophils was observed and surprisingly, granulocytes comprised a greater proportion of infected phagocytes than alveolar macrophage. By 7 days post-infection alveolar macrophages had become the dominant BCG-associated phagocytes. Prior mucosal BCG exposure provided immunised mice with greater frequencies and numbers of lung macrophage subsets, and a significantly greater proportion of alveolar macrophages expressed CD11b prior to and following challenge infection. These data provide the first evidence of granulocytes as the dominant infected phagocyte subset early after mycobacterial infection, and highlight enhanced recruitment of lung macrophages as a factor associated with protection in BCG-immunised mice.