Background - Immunity to malaria develops naturally in endemic regions, but the protective immune mechanisms are poorly understood. Many vaccination strategies aim to induce T cells against diverse pre-erythrocytic antigens, but correlates of protection in the field have been limited. The objective of this study was to investigate cell-mediated immune correlates of protection in natural malaria. Memory T cells reactive against thrombospondin-related adhesive protein (TRAP) and circumsporozoite (CS) protein, major vaccine candidate antigens, were measured, as were frequencies of CD4+ CD25high T cells, which may suppress immunity, and CD56+ NK cells and γδ T cells, which may be effectors or may modulate immunity. Methodology and Principal Findings - 112 healthy volunteers living in rural Kenya were entered in the study. Memory T cells reactive against TRAP and CS were measured using a cultured IFNγ ELISPOT approach, whilst CD4+ CD25high T cells, CD56+ NK cells, and γδ T cells were measured by flow cytometry. We found that T cell responses against TRAP were established early in life (<5 years) in contrast to CS, and cultured ELISPOT memory T cell responses did not correlate with ex-vivo IFNγ ELISPOT effector responses. Data was examined for associations with risk of clinical malaria for a period of 300 days. Multivariate logistic analysis incorporating age and CS response showed that cultured memory T cell responses against TRAP were associated with a significantly reduced incidence of malaria (p = 0.028). This was not seen for CS responses. Higher numbers of CD4+ CD25high T cells, potentially regulatory T cells, were associated with a significantly increased risk of clinical malaria (p = 0.039). Conclusions - These data demonstrate a role for central memory T cells in natural malarial immunity and support current vaccination strategies aimed at inducing durable protective T cell responses against the TRAP antigen. They also suggest that CD4+ CD25high T cells may negatively affect naturally acquired malarial immunity.