Background: Crucial connections between sexual network structure and the distribution of HIV remain inadequately understood, especially in regard to the role of concurrency and age disparity in relationships, and how these network characteristics correlate with each other and other risk factors. Social desirability bias and inaccurate recall are obstacles to obtaining valid, detailed information about sexual behaviour and relationship histories. Therefore, this study aims to use novel research methods in order to determine whether HIV status is associated with age-disparity and sexual connectedness as well as establish the primary behavioural and socio-demographic predictors of the egocentric and community sexual network structures. Method/Design. We will conduct a cross-sectional survey that uses a questionnaire exploring one-year sexual histories, with a focus on timing and age disparity of relationships, as well as other risk factors such as unprotected intercourse and the use of alcohol and recreational drugs. The questionnaire will be administered in a safe and confidential mobile interview space, using audio computer-assisted self-interview (ACASI) technology on touch screen computers. The ACASI features a choice of languages and visual feedback of temporal information. The survey will be administered in three peri-urban disadvantaged communities in the greater Cape Town area with a high burden of HIV. The study communities participated in a previous TB/HIV study, from which HIV test results will be anonymously linked to the survey dataset. Statistical analyses of the data will include descriptive statistics, linear mixed-effects models for the inter- and intra-subject variability in the age difference between sexual partners, survival analysis for correlated event times to model concurrency patterns, and logistic regression for association of HIV status with age disparity and sexual connectedness. Discussion. This study design is intended to facilitate more accurate recall of sensitive sexual history data and has the potential to provide substantial insights into the relationship between key sexual network attributes and additional risk factors for HIV infection. This will help to inform the design of context-specific HIV prevention programmes.