HIV transmission is most likely to occur during the first few months after infection, yet few cases are identified during this period. Using a population-based cohort of young Malawian women, we identify the distinct symptomology and health-seeking behavior marking early HIV infection (EHI) by comparing it to periods of seronegativity and chronic infection. During EHI women are more likely to report malaria-like symptoms and visit clinics for malaria care. In malaria-endemic contexts, where acute HIV symptoms are commonly mistaken for malaria, early diagnostic HIV testing and counseling should be integrated into healthcare settings where people commonly seek treatment for malaria.