Genome-wide searches for loci involved in human resistance to malaria are currently being conducted on a large scale in Africa using case-control studies. Here, we explore the utility of an alternative approach - "environmental correlation analysis, ECA", which tests for clines in allele frequencies across a gradient of an environmental selection pressure - to identify genes that have historically protected against death from malaria. We collected genotype data from 12,425 newborns on 57 candidate malaria resistance loci and 9,756 SNPs selected at random from across the genome, and examined their allele frequencies for geographic correlations with long-term malaria prevalence data based on 84,042 individuals living under different historical selection pressures from malaria in coastal Kenya. None of the 57 candidate SNPs showed significant (P < 0.05) correlations in allele frequency with local malaria transmission intensity after adjusting for population structure and multiple testing. By contrast, two of the random SNPs that had highly significant correlations (P < 0.01) were in genes previously linked to malaria resistance, namely, CDH13, encoding cadherin 13, and HS3ST3B1, encoding heparan sulphate 3-O-sulfotransferase 3B1. Both proteins play a role in glycoprotein-mediated cell-cell adhesion which has been widely implicated in cerebral malaria, the most life-threatening form of this disease. Other top genes, including CTNND2 which encodes δ-catenin, a molecular partner to cadherin, were significantly enriched in cadherin-mediated pathways affecting inflammation of the brain vascular endothelium. These results demonstrate the utility of ECA in the discovery of novel genes and pathways affecting infectious disease.