The rapid spread of the SARS-CoV-2 Omicron (B.1.1.529) variant, including in highly vaccinated populations, has raised important questions about the efficacy of current vaccines. In this study, we show that the mRNA-based BNT162b2 vaccine and the adenovirus-vector-based Ad26.COV2.S vaccine provide robust protection against high-dose challenge with the SARS-CoV-2 Omicron variant in cynomolgus macaques. We vaccinated 30 macaques with homologous and heterologous prime-boost regimens with BNT162b2 and Ad26.COV2.S. Following Omicron challenge, vaccinated macaques demonstrated rapid control of virus in bronchoalveolar lavage, and most vaccinated animals also controlled virus in nasal swabs. However, 4 vaccinated animals that had moderate Omicron-neutralizing antibody titers and undetectable Omicron CD8+ T cell responses failed to control virus in the upper respiratory tract. Moreover, virologic control correlated with both antibody and T cell responses. These data suggest that both humoral and cellular immune responses contribute to vaccine protection against a highly mutated SARS-CoV-2 variant. Display omitted •Ad26.COV2.S and BNT162b2 led to rapid virologic control following Omicron challenge•Both Omicron-specific antibodies and T cells contributed to protection•Virologic failure correlated with moderate antibodies and negligible CD8+ T cells Heterologous as well as homologous prime-boosting with the mRNA vaccine BNT162b2 and adenovirus-vector-based Ad26.COV2.S vaccine provides robust protection against SARS-CoV-2 Omicron in cynomolgus macaques, with both humoral and cellular immune responses being critical for overall protection.