Many non-mucosal vaccines are poorly protective against mucosal pathogens, presumably because they do not generate mucosa-tropic memory cells. Few mucosal vaccines are in clinical use because live vaccine vectors pose safety risks and killed or molecular antigens (Ags) are weak immunogens when applied to intact mucosa. Adjuvants can potentially overcome this poor immunogenicity, however, conventional mucosal adjuvants possess unfavorable safety profiles. We have developed an adjuvanted vaccine against Chlamydia trachomatis. Genital Ct infection induced protective immunity that depended on interferon-γ (IFN-γ) producing CD4 T-cells, whereas mucosal exposure to UV-inactivated Ct (UV-Ct) generated tolerogenic Ct-specific regulatory T-cells, resulting in exacerbated bacterial burden upon Ct challenge. However, mucosal immunization with UV-Ct complexed with charge-switching synthetic adjuvant particles (cSAP) did not exert the tolerogenic effect of UV-Ct alone but elicited long-lived protection. This differential effect of UV-Ct-cSAP versus UV-Ct was because the former was presented by immunogenic CD11b⁺CD103^–dendritic cells (DCs), while the latter was acquired by tolerogenic CD11b^–CD103⁺ DCs. Genital protection was achieved after intrauterine or intranasal, but not subcutaneous vaccination and was inducible in conventional and humanized mice. Regardless of vaccination route, UV-Ct-cSAP induced robust systemic memory cells. However, only mucosal vaccination induced a wave of Ct-specific effector T-cells that seeded the mucosa during the first week and established resident memory T cells (T_RM). Without T_RM, mice were suboptimally protected, even when circulating memory cells were abundant. For optimal Ct clearance, both early seeding by T_RM and infection-induced recruitment of a second wave of circulating memory cells were required. Thus, using a novel mucosal vaccine platform, we demonstrate that protection against Ct depends on synergistic actions of two memory T cell subsets with distinct migratory properties.