Thalassemias are inherited blood disorders that are found in high prevalences in the Mediterranean, Southeast Asia and the Pacific. These diseases provide varying levels of resistance to malaria and are proposed to have emerged as an adaptive response to malaria in these regions. The transition to agriculture in the Holocene has been suggested to have influenced the selection for thalassemia in the Mediterranean as land clearance for farming encouraged interaction between Anopheles mosquitos, the vectors for malaria, and human groups. Here we document macroscopic and microscopic skeletal evidence for the presence of thalassemia in both hunter-gatherer (Con Co Ngua) and early agricultural (Man Bac) populations in northern Vietnam. Firstly, our findings demonstrate that thalassemia emerged prior to the transition to agriculture in Mainland Southeast Asia, from at least the early seventh millennium BP, contradicting a long-held assumption that agriculture was the main driver for an increase in malaria in Southeast Asia. Secondly, we describe evidence for significant malarial burden in the region during early agriculture. We argue that the introduction of farming into the region was not the initial driver of the selection for thalassemia, as it may have been in other regions of the world.