The presence of inhibitory immune cells and difficulty in generating activated effector T cells remain obstacles to development of effective cancer vaccines. We designed a vaccine regimen combining human telomerase reverse transcriptase (hTERT) peptides with concomitant therapies targeting regulatory T cells (Tregs) and cyclooxygenase-2 (COX2)-mediated immunosuppression. This Phase 1 trial combined an hTERT-derived 7-peptide library, selected to ensure presentation by both HLA class-I and class-II in 90% of patients, with oral low-dose cyclophosphamide (to modulate Tregs) and the COX2 inhibitor celecoxib. Adjuvants were Montanide and topical TLR-7 agonist, to optimise antigen presentation. The primary objective was determination of the safety and tolerability of this combination therapy, with anti-cancer activity, immune response and detection of antigen-specific T cells as additional endpoints. Twenty-nine patients with advanced solid tumours were treated. All were multiply-pretreated, and the majority had either colorectal or prostate cancer. The most common adverse events were injection-site reactions, fatigue and nausea. Median progression-free survival was 9 weeks, with no complete or partial responses, but 24% remained progression-free for ≥6 months. Immunophenotyping showed post-vaccination expansion of CD4+ and CD8+ T cells with effector phenotypes. The in vitro re-challenge of T cells with hTERT peptides, TCR sequencing, and TCR similarity index analysis demonstrated the expansion following vaccination of oligoclonal T cells with specificity for hTERT. However, a population of exhausted PD-1+ cytotoxic T cells was also expanded in vaccinated patients. This vaccine combination regimen was safe and associated with antigen-specific immunological responses. Clinical activity could be improved in future by combination with anti-PD1 checkpoint inhibition to address the emergence of an exhausted T cell population.