Understanding informal leadership in high HIV prevalence settings is important for the success of popular opinion leader (POL) and other HIV testing and treatment promotion strategies which aim to leverage the influence of these leaders. We conducted a study in Mpumalanga province, South Africa, in which we aimed to: (1) describe men's personal networks and key social relationships; and (2) describe the types of individuals men identify as leaders. We administered a structured questionnaire with 45 men (15 HIV-positive and 30 HIV-negative) in which men enumerated and described characteristics of individuals they share personal matters with, and people they considered as leaders. We further conducted in-depth interviews with 25 of these men to better understand men's conceptualisation of leadership in their community. Family members were prominent in men's personal networks and among the leaders they nominated. Men living with HIV were much more likely to know others living with HIV, and described friendships on the basis of the shared experience of HIV treatment. Future POL interventions aiming to promote HIV testing and care among men in rural South Africa should consider the importance of family in community leadership, and seek to leverage the influence of connections between men living with HIV.