Infection with human immunodeficiency virus (HIV) is associated with neuroimaging alterations. However, little is known about the topological organization of whole-brain networks and the corresponding association with cognition. As such, we examined structural whole-brain white matter connectivity patterns and cognitive performance in 29 HIV+ young adults (mean age = 25.9) with limited or no HIV treatment history. HIV+ participants and demographically similar HIV- controls (n = 16) residing in South Africa underwent magnetic resonance imaging (MRI) and neuropsychological testing. Structural network models were constructed using diffusion MRI-based multifiber tractography and T1-weighted MRI-based regional gray matter segmentation. Global network measures included whole-brain structural integration, connection strength, and structural segregation. Cognition was measured using a neuropsychological global deficit score (GDS) as well as individual cognitive domains. Results revealed that HIV+ participants exhibited significant disruptions to whole-brain networks, characterized by weaker structural integration (characteristic path length and efficiency), connection strength, and structural segregation (clustering coefficient) than HIV- controls (p < 0.05). GDSs and performance on learning/recall tasks were negatively correlated with the clustering coefficient (p < 0.05) in HIV+ participants. Results from this study indicate disruption to brain network integrity in treatment-limited HIV+ young adults with corresponding abnormalities in cognitive performance.