Invasion of non-native riparian vegetation along southwestern USA rivers is associated with channel narrowing and simplification, prompting numerous and varied removal efforts. Channel width and migration rate often, but not always, increase following treatment. The cause of this variability and the duration of response is poorly understood. Using flow records and aerial imagery we quantified measurement uncertainty, change in channel width and rates of floodplain formation and erosion relative to annual peak flows before and during the invasion of Russian olive (Elaeagnus angustifolia L.), and following removal, along the Escalante River, Utah, over a fifty-year period. Prior to the invasion, the Escalante River was undergoing a decades-long narrowing process following large, turn-of-the-20th-century floods. Russian olive created a unique geomorphic shift in the observed pattern of channel change. Dense, channel-edge establishment and morphological traits including dense, inflexible branches, resulted in enhanced channel narrowing. Because the initial spread of Russian olive was from upstream to downstream, the Russian olive forest was wider and older upstream than downstream. Consequently, channel narrowing was greater and floodplain erosion rates had already decreased in upstream reaches compared to downstream. Russian olive removal increased channel width and floodplain erosion rates in upstream reaches, where Russian olive was most abundant. In contrast, downstream reaches continued to narrow. Small but detectable increases in rates of floodplain erosion across all reaches, and increased sinuosity in some, suggest the channel is becoming more mobile in the absence of Russian olive. Results indicate channel adjustment to Russian olive removal is spatially variable and may take a decade or more. With continued expansion of native riparian vegetation, future narrowing is likely during sustained low peak flows and large-scale widening is unlikely in the absence of extreme floods or physical removal of existing riparian vegetation.