Southeast Asian Ovalocytosis (SAO) is a common red blood cell disorder that is maintained as a balanced polymorphism in human populations. In individuals heterozygous for the SAO-causing mutation there are minimal detrimental effects and well-documented protection from severe malaria caused by Plasmodium vivax and Plasmodium falciparum; however, the SAO-causing mutation is fully lethal in utero when homozygous. The present-day high frequency of SAO in Island Southeast Asia indicates the trait is maintained by strong heterozygote advantage. Our study elucidates the evolutionary origin of SAO by characterizing DNA sequence variation in a 9.5 kilobase region surrounding the causal mutation in the SLC4A1 gene. We find substantial haplotype diversity among SAO chromosomes and estimate the age of the trait to be approximately 10,005 years (95% CI: 4930-23,200 years). This date is far older than any other human malaria-resistance trait examined previously in Southeast Asia, and considerably pre-dates the widespread adoption of agriculture associated with the spread of speakers of Austronesian languages some 4000 years ago. Using a genealogy-based method we find no evidence of historical positive selection acting on SAO (s=0.0, 95% CI: 0.0-0.03), in sharp contrast to the strong present-day selection coefficient (e.g., 0.09) estimated from the frequency of this recessively lethal trait. This discrepancy may be due to a recent increase in malaria-driven selection pressure following the spread of agriculture, with SAO targeted as a standing variant by positive selection in malarial populations.