Malawi is one of 14 priority countries for voluntary medical male circumcision (VMMC) initiatives with the lowest VMMC uptake. Using data from a study of 269 men accessing VMMC in southern Malawi and latent class analysis, men were classified based on four risk factors: ever tested for HIV, condom use at last sex, having casual/concurrent sexual partners, and using alcohol before sex. Two distinct classes were identified: 8% of men were classified as high risk, while 92% were classified as low/medium risk. Poisson regression modeling indicated that men who had lower education (risk ratio [RR] 1.07, p < 0.05) and were ages 19–26 (RR 1.07, p < 0.05) were more likely to be in the high risk group. The low numbers of men in the high risk category seeking services suggests the need to implement targeted strategies to increase VMMC uptake among such high risk men.