Many real world applications require large-scale sensor networks deployed on the surface of a complex 3D terrain. Compared with planar and 3D network localizations, terrain surface network localization generates unique and fundamental hardness. We explore 3D surface network localization with terrain models. A digital terrain model (DTM), available to public with a variable resolution up to one meter, is a 3D representation of a terrain's surface. The constraint that the sensors must be on the known 3D terrain's surface ensures that the triangular meshes of the network and the terrain's surface overlap and approximate the same geometric shape. The basic idea of both the anchor-based and anchor-free localization algorithms is to map the two triangular meshes extracted from the connectivity graph of a sensor network and the DTM of its deployed terrain surface to plane. With the well-aligned triangular meshes of a network and its deployed terrain surface on plane, each sensor node of the network can easily locate reference grid points from the DTM of the terrain to calculate its own geographic location.