Tin mine tailings (TMT) and fuming slag (FS) contain many heavy metals (As, Cr, Cu, Zn and Mn) that cause severe pollution to the environment. Herein, geopolymers were prepared using TMT, FS and flue gas desulfurization gypsum (FGDG) to immobilize heavy metals, and their compressive strength and heavy metal leaching toxicity were investigated. It was first determined that T4F5 (TMT:FS = 4:5) sample exhibited the highest compressive strength (7.83 MPa). T4F5 achieved 95% immobilization efficiency for As and Cr, and nearly 100% for Cu, Zn and Mn, showing good immobilization performance. A series of characterization analyses showed that heavy metal cations can balance the charge in the geopolymer and replace Al in the geopolymer structure to form covalent bonds. In addition, about 2%-20% of heavy metal Fe was immobilized in hydration products, heavy metal hydroxides and non-bridging Si-O and Al-O coordination with silica-aluminate matrices. AsO33- was oxidized into AsO43-, which may form Ca-As or Fe-As precipitates. Cr2O72- was converted to CrO42- under alkaline environment and then combined with OH- to form Cr(OH)3 precipitates. Mn2+ may react directly with dissolved silicate to form Mn2SiO4 and also form Mn(OH)2 precipitates. The unstable Mn(OH)2 can be further oxidized to MnO2. The heavy metal cations were immobilized in the silicoaluminate lattice, while the anions tended to form insoluble precipitates. These results may benefit the industry and government for better handling of TMT, FS and solid wastes containing the abovementioned five heavy metals.