Amyotrophic lateral sclerosis (ALS) is a severe neurodegenerative disease selectively affecting upper and lower motor neurons. Patients with ALS suffer from progressive paralysis and eventually die on average after three years. The underlying neurobiology of upper motor neuron degeneration and its effects on the complex network of the brain are, however, largely unknown. Here, we examined the effects of ALS on the structural brain network topology in 35 patients with ALS and 19 healthy controls. Using diffusion tensor imaging (DTI), the brain network was reconstructed for each individual participant. The connectivity of this reconstructed brain network was compared between patients and controls using complexity theory without - a priori selected - regions of interest. Patients with ALS showed an impaired sub-network of regions with reduced white matter connectivity (p = 0.0108, permutation testing). This impaired sub-network was strongly centered around primary motor regions (bilateral precentral gyrus and right paracentral lobule), including secondary motor regions (bilateral caudal middle frontal gyrus and pallidum) as well as high-order hub regions (right posterior cingulate and precuneus). In addition, we found a significant reduction in overall efficiency (p = 0.0095) and clustering (p = 0.0415). From our findings, we conclude that upper motor neuron degeneration in ALS affects both primary motor connections as well as secondary motor connections, together composing an impaired sub-network. The degenerative process in ALS was found to be widespread, but interlinked and targeted to the motor connectome.