HIV testing is the entry point to the cascade of services within HIV care. Although Malawi has made positive strides in HIV testing, men are lagging at 65.5% while women are at 81.6%. This study explored the preferences of men on the avenues for HIV testing in Blantyre, Malawi. This was a descriptive qualitative study in the phenomenological tradition in seven public health facilities in Blantyre, Malawi, among men and health-care workers (HCWs). We conducted 20 in-depth interviews and held 14 focus group discussions among 113 men of varying HIV statuses. All our participants were purposively selected, and data were digitally recorded coded and managed through NVivo. Thematic analysis was guided by the differentiated service delivery model. Men reported a preference for formal and informal workplaces such as markets and other casual employment sites; social places like football pitches, bars, churches, and "bawo" spaces; and outreach services in the form of weekend door-to-door, mobile clinics, men-to-men group. The health facility was the least preferred avenue. The key to testing men for HIV is finding them where they are. Areas that can be leveraged in reaching men are outside the routine health system. Scaling up HIV testing among men will require targeting avenues and operations outside of the routine health system and leverage them to reach more men with services. This suggests that HIV testing and counseling (HTC) uptake among men may be increased if the services were provided at informal places.