Abstract: Artisanal gold-mining (AGM) is one of the most important activities in the districts of Migori and Transmara (Kenya). Gold-mining, however, is known to release vast quantities of arsenic and metals (some of which are very toxic like As, Hg, Cd, or Pb), which poses a serious threat to not only miners but also to the ecosystem and local populations. We, herein, determine the concentrations of arsenic and some heavy metals in several sample types (i.e., ore, soil, river sediment, and mine tailing) collected from the districts of Migori and Transmara. We also employ lichens and mosses as pollution bioindicators. Geostatistical tools and canonical correlation analysis were used to identify the relevant factors that affected arsenic and metal concentrations in the analysed samples. The following concentration ranges were reported in topsoil: As (1–17,250 mg kg−1), Cd (0.01–15.10 mg kg−1), Cu (7–9,238 mg kg−1), Cr (1–214 mg kg−1), Ni (5–766 mg kg−1), Pb (3–1,149 mg kg−1), and Zn (22–1,271 mg kg−1). It was concluded that the ecosystem in both districts was highly polluted by heavy metals whereas the arsenic concentrations in topsoil were among the highest reported worldwide. The results of this study provide new evidence on the impact of AGM on the environment and may further contribute to the design of policy measures with the aim of reducing environmental and human health risks associated to AGM activities.