Old age and possession of the APOE-4 allele are the two main risk factors for developing later onset Alzheimer's Disease (AD). Carriers of the APOE-4 allele have known differences in intrinsic functional brain network activity across the life span. These individuals also demonstrate specific regional differences in gray and white matter gross structure. However, the relationship of these variations to whole brain structural network connectivity remains unclear. We performed diffusion tensor imaging (DTI), T1 structural imaging, and cognitive testing on aging APOE-4 noncarriers (n = 30; mean age = 63.8±8.3) and APOE-4 carriers (n = 25; mean age = 60.8 ±9.7). Fiber tractography was used to derive whole brain structural graphs, and graph theory was applied to assess structural network properties. Network communication efficiency was determined for each network by quantifying local interconnectivity, global integration, and the balance between these, the small worldness. Relative to noncarriers, APOE-4 carriers demonstrated an accelerated age-related loss of mean local interconnectivity (r = -0.64, P ≤ 0.01) and regional local interconnectivity decreases in the precuneus (r = -0.64), medial orbitofrontal cortex (r = -0.5), and lateral parietal cortex (r = -0.54). APOE-4 carriers also showed significant age-related loss in mean cortical thickness (r = -0.52, P < 0.05). Cognitively, APOE-4 carriers had significant negative correlations of age and performance on two episodic memory tasks (P < 0.05). This genotype-specific pattern of structural connectivity change with age thus appears related to changes in gross cortical structure and cognition, potentially affecting the rate and/or spatial distribution of AD-related pathology.