Objective We pilot tested a Motivational Interviewing (MI) –based counseling intervention for individuals with Acute HIV Infection (AHI) to reduce risky sexual behavior in Lilongwe, Malawi. Methods Twenty-eight individuals diagnosed with AHI were randomized to receive either brief education alone, or the brief education plus the MI-based intervention, called Uphungu Wanga. Participants in Uphungu Wanga received four sessions delivered on the day of diagnosis, three days later and at weeks 1 and 2 with a booster session at week 8; participants were followed for 24 weeks from diagnosis. An interviewer administered quantitative questionnaire was conducted at baseline and at weeks 2, 4, 8, 12, 16, 20 and 24. Semi-structured qualitative interviews (SSI) were conducted at weeks 2, 8, 12, and 24. Results The majority of participants in both arms reported rapid and sustained behavior change following diagnosis with AHI. Very few participants reported having sex without a condom after diagnosis. Participants reported a trend towards fewer sex partners and abstaining from sex during study follow-up. Participants in the MI-based arm provided concrete examples of risk reduction strategies in the SSIs while those in the brief education arm primarily described reducing risk behavior, suggesting that the MI-based group may have acquired more risk reduction skills. Conclusions Individuals in both study arms reduced risky sexual behaviors after diagnosis with AHI. We found few major differences between study arms during the 6-month follow up period in self-reported sexual behaviors therefore a MI-based intervention may not be needed to trigger behavior change following AHI. However, comparing the MI-based intervention to repeated brief education sessions made it difficult to assess the potential benefit of an MI-based intervention in a setting where standard counseling often consists of one post-test session. Nevertheless, provision of counseling immediately following diagnosis with HIV to support behavior change should remain a priority. Trial Registration ClinicalTrials.gov NCT01197027