The spread of non-native fish species is increasing globally and threatening aquatic ecosystems. Identifying the origins, the pathways, and vectors is crucial for managing biological invasions. We conducted a genetic characterization of Arapaima gigas from the Madeira River, considering native and non-native populations, to elucidate the invasion of the upper and middle Madeira River basin by A. gigas. We analyzed 9 microsatellite loci of 141 individuals from native (lower Madeira) and invasive (upper Madeira) populations, in addition to a locality from Peru outside the Madeira River basin drainage area, that previously was suggested to be one of the possible origins of the invasion. The results of discriminant analysis of principal components, Bayesian modeling of population structure, clustering and assignment tests (using microsatellite data from other Amazon locations) showed a clear separation between native and invasive populations and revealed a mixture of individuals from upper and middle Madeira and Peru. We confirm that the invasive population originates from Peru and was introduced by fish escapees from farms. Multiple secondary introductions may have advanced the invasion speed. Such a scenario represents a conservation paradox, because in its native habitat, A. gigas is endangered, whereas it has become invasive in non-native areas.