Neoantigens (nAgs) are promising tumor antigens for cancer vaccination with the potential of inducing robust and selective T cell responses. Genetic vaccines based on Adenoviruses derived from non-human Great Apes (GAd) elicit strong and effective T cell-mediated immunity in humans. Here, we investigate for the first time the potency and efficacy of a novel GAd encoding multiple neoantigens. Prophylactic or early therapeutic vaccination with GAd efficiently control tumor growth in mice. In contrast, combination of the vaccine with checkpoint inhibitors is required to eradicate large tumors. Gene expression profile of tumors in regression shows abundance of activated tumor infiltrating T cells with a more diversified TCR repertoire in animals treated with GAd and anti-PD1 compared to anti-PD1. Data suggest that effectiveness of vaccination in the presence of high tumor burden correlates with the breadth of nAgs-specific T cells and requires concomitant reversal of tumor suppression by checkpoint blockade.