Malaria vaccines based on polyepitope constructs that elicit cell-mediated immunity against a broad spectrum of malaria parasites and which cover the majority of HLA alleles are provided. Epitopes in the polyepitope constructs are from regions of the Plasmodium falciparum circumsporozoite protein (CSP) known to contain CD4 and CD8 T cell epitopes, and include both epitopes from highly variable and highly conserved regions of CSP.