Knowledge of the spatial distribution of heavy metals is indispensable for successful risk analysis of contaminated sites. The common practice is to obtain soil samples for spatial interpolation through site investigation, which generally involves preliminary and detailed surveys. In this study, we propose an information entropy-based site investigation (IESI) method in which an optimal design step is implemented to guide soil sampling at the detailed survey stage. Two types of information entropy (i.e., relative entropy and Shannon entropy) are used to design the optimal sampling strategy. The results show that, within the IESI method, relative entropy is superior to Shannon entropy in guiding soil sampling. Combined with ordinary kriging, the IESI method outperforms conventional surveys for hypothetical and actual heavy metal-contaminated sites as it can identify new polluted and clean areas. For quantitative comparisons, the IESI method coupled with ordinary kriging, logarithmic ordinary kriging, and universal kriging with linear and quadratic trends can improve the interpolation accuracy by 16–43% at the actual heavy metal-contaminated site. Upon further examination of the IESI method, informative sampling points are mainly distributed around the polluted areas identified by the preliminary survey with soil pollution probabilities between 0.75 and 0.95. This work provides an effective tool for delineating the spatial distribution and valuable insights into identifying encryption areas at heavy-metal sites.