The sum of all of the interactions between single bacteria and host cells determines if an infection is cleared, controlled, or progresses at the whole host-organism level. These individual interactions have independent trajectories defined by diverse and dynamic host-cell and bacterial responses. Focusing on Mycobacterium tuberculosis infection, we discuss how advances in single-cell technologies allow investigation of heterogeneity in host-pathogen interactions and how different layers of heterogeneity in the host affect disease outcome. At late stages of infection, many single interactions co-exist and different outcomes depend on inter-granuloma and intra-granuloma heterogeneity. However, during bottleneck events involving small numbers of bacteria, random events, such as chance interactions with more or less permissive host cells, play a decisive role and may explain why some exposed individuals never develop the disease.