Cholera is a disease of significant global health burden, characterised by acute watery diarrhoea and severe dehydration, and caused by the Gram-negative bacterium Vibrio cholerae. Of the nearly 200 V. cholerae serogroups based on the O-antigen-specific polysaccharide, only isolates of O1 and O139 that also carry cholera toxin have caused epidemics and pandemics. The 2023 - 2024 cholera outbreak in Zambia is part of the seventh global cholera pandemic, and resulted in approximately 20,000 cases and 700 deaths. A whole-cell-killed, bivalent O1/O139 oral cholera vaccine was used to aid outbreak control. Here, we investigated the role of the cellular immune response in long-term adaptive immunity to cholera infection and vaccination during this outbreak. Through serological assays, we found that natural infection induced more durable immunity than vaccination alone or vaccination followed by breakthrough infection. We leveraged next-generation single-cell RNA sequencing of re-infected peripheral blood mononuclear cells to contrast the heterogeneity in gene expression between vaccinated and convalescent cholera patients. We sequenced B-cell receptor repertoires at single-cell resolution to define clonotypes that are shared across or unique to these groups, and identified cell type-specific transcriptomic signatures associated with the stronger memory responses in naturally infected patients. Finally, by integrating host immune profiles with gut microbiome composition derived from metagenomic sequencing, we found associations between microbial carriage patterns and immune phenotypes. Together, these findings provide insight into the mechanisms of long-term immunity to V. cholerae, to help identify candidate correlates of protection and suggest strategies to improve vaccine deployment in outbreak control.