The Tianshuihai lead–zinc deposit, located in the Karakorum Mountains, Xinjiang Province, NW China, was discovered in 2011. The ore bodies occur within the clastic rocks in the lower part of the Cretaceous Tielongtan Group. The main ore body of the mineral deposit is 450 m in length, 5.24–47.5 m in thickness and 201 m in depth. It strikes NE and dips SE at about 50°, which is consistent with the occurrence of its surrounding rock layers. This lead–zinc deposit with an average Pb grade of 6.65% (ranging from 0.5% to 58.5%) has potential for becoming a large-scale deposit. The discovery of this deposit is a result of a stepwise multi-scale geochemical mapping program including an original geochemical exploration with very low density (1 point/16 km²), followed by general exploration (4 points/km²), then mineral prospecting (125 points/km²), and finally with drilling verification. As a consequence, this is a successful case of multi-scale geochemical mapping for exploration of metallic mineral resources.