The accumulation of amyloid plaques is one of the earliest pathological changes in Alzheimer's disease (AD) and may occur 20 years before the onset of symptoms. Examining associations between amyloid pathology and other early brain changes is critical for understanding the pathophysiological underpinnings of AD. Alterations in gray matter networks might already start at early preclinical stages of AD. In this study, we examined the regional relationship between amyloid aggregation measured with positron emission tomography (PET) and gray matter network measures in elderly subjects with subjective memory complaints. Single-subject gray matter networks were extracted from T1-weigthed structural MRI in cognitively normal subjects (n = 318, mean age 76.1 ± 3.5, 64% female, 28% amyloid positive). Degree, clustering, path length and small world properties were computed. Global and regional amyloid load was determined using [ 18 F]-Florbetapir PET. Associations between standardized uptake value ratio (SUVr) values and network measures were examined using linear regression models. We found that higher global SUVr was associated with lower clustering (β = −0.12, p < 0.05), and small world values (β = −0.16, p < 0.01). Associations were most prominent in orbito-and dorsolateral frontal and parieto-occipital regions. Local SUVr values showed less anatomical variability and did not convey additional information beyond global amyloid burden. In conclusion, we found that in cognitively normal elderly subjects, increased global amyloid pathology is associated with alterations in gray matter networks that are indicative of incipient network breakdown towards AD dementia.