This study aims to handle an integrated evaluation of soil and stream sediment geochemical data to evaluate source apportionment and to establish geochemical threshold variations for Fe, Al, and 20 selected Potentially Toxic Elements (PTE) in the Parauapebas River Basin (PB), Eastern Amazon. The data set used in this study is from the Itacaiúnas Geochemical Mapping and Background Project (ItacGMBP), which collected 364 surface soil (0–10 cm) samples and 189 stream sediments samples in the entire PB. The <0.177 mm fraction of these samples were analyzed for 51 elements by ICP-MS and ICP-AES, following an aqua regia digestion. The geochemical maps of many elements revealed substantial differences between the north (NPB) and the south (SPB) of PB, mainly due to the geological setting. The new statistically derived threshold values of the NPB and SPB regions were compared to the threshold of the whole PB, reported in previous studies, and to quality guidelines proposed by Brazilian environmental agencies. The natural variation of geochemical background in soils and stream sediments of PB should be considered prior to defining new guideline values. At the regional scale, the local anomalies are mostly influenced by the predominant lithology rather than any anthropogenic impact.