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+ individuals 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 multi-fiber 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+ individuals exhibited significant disruptions to whole-brain networks, characterized by weaker structural integration (characteristic path length and efficiency), connection strength, and structural segregation (clustering coefficient) compared to HIV– controls (p values < 0.05). GDS scores and performance on learning/recall tasks were negatively correlated with the clustering coefficient (p < 0.05) in HIV+ individuals. Results from the present study indicate disruption to brain network integrity in young, treatment limited HIV+ individuals with corresponding abnormalities in cognitive performance.