Digital elevation model (DEM) co-registration is one of the hottest research problems, and it is the critical technology for multi-temporal DEM analysis, which has wide potential application in many fields, such as geological hazards. Currently, the least-squares principle is used in most DEM co-registration methods, in which the matching parameters are obtained by iteration; the surface co-registration is then accomplished. To improve the iterative convergence rate, a Gauss-Newton method for DEM co-registration (G-N) is proposed in this paper. A gradient formula based on a gridded discrete surface is derived in theory, and then the difficulty of applying the Gauss-Newton method to DEM matching is solved. With the G-N algorithm, the surfaces approach each other along the maximal gradient direction, and therefore the iterative convergence and the performance efficiency of the new method can be enhanced greatly. According to experimental results based on the simulated datasets, the average convergence rates of rotation and translation parameters of the G-N algorithm are increased by 40 and 15% compared to those of the ICP algorithm, respectively. The performance efficiency of the G-N algorithm is 74.9% better.