The Ponto-Caspian goby Neogobius melanostomus (Pallas 1814) is a widespread non-native fish species in European rivers. It occurs in high abundance and can potentially alter the food webs of invaded water bodies profoundly. However, the invasion process usually goes unnoticed, and changes in food webs during the early stages of invasions are rarely described. Here, we studied populations of N. melanostomus along an invasion gradient in the Elbe River (Germany) and tested the effects of time since invasion on the diets and the associated trophic dynamics in two dominant habitats, i.e., rip rap and sand. Results showed that the abundance and biomass of N. melanostomus was lowest at the most recently invaded sites. The trophic niche space quantified by stable isotopes (δ ¹³ C and δ ¹⁵ N) showed that populations at earlier invaded sites exhibited a wider trophic niche than those at the most recently invaded sites. Diptera and Crustacea were the most abundant taxa in N. melanostomus guts at both habitat structures. At rip rap habitats, N. melanostomus showed a significant increasing preference for Crustacea and a decreasing one for Gastropoda along the invasion gradient. At sand habitats no significant relationships between the invasion gradient and electivity index for N. melanostomus were detected. We demonstrated that the invasion stage and habitat in which N. melanostomus occurs affect the feeding preference of this invasive fish and that these factors are therefore important for tracing changes in the macroinvertebrate communities of affected river systems.