Neuronal nitric oxide synthase (nNOS) neurons play a fundamental role in inhibitory neurotransmission, within the enteric nervous system (ENS), and in the establishment of gut motility patterns. Clinically, loss or disruption of nNOS neurons has been shown in a range of enteric neuropathies. However, the effects of nNOS loss on the composition and structure of the ENS remain poorly understood. The aim of this study was to assess the structural and transcriptional consequences of loss of nNOS neurons within the murine ENS. Expression analysis demonstrated compensatory transcriptional upregulation of pan neuronal and inhibitory neuronal subtype targets within the Nos1−/− colon, compared to control C57BL/6J mice. Conventional confocal imaging; combined with novel machine learning approaches, and automated computational analysis, revealed increased interconnectivity within the Nos1−/− ENS, compared to age-matched control mice, with increases in network density, neural projections and neuronal branching. These findings provide the first direct evidence of structural and molecular remodelling of the ENS, upon loss of nNOS signalling. Further, we demonstrate the utility of machine learning approaches, and automated computational image analysis, in revealing previously undetected; yet potentially clinically relevant, changes in ENS structure which could provide improved understanding of pathological mechanisms across a host of enteric neuropathies.