This paper presents a new algorithm for solving the well-known traveling salesman problem (TSP). This algorithm applies the Distance Matrix Method to the Greedy heuristic that is widely used in the TSP literature. In particular, it is shown that there exists a significant negative correlation between the variance of distance matrix and the performance of the Greedy heuristic, that is, the less the variance of distance matrix among the customer nodes is, the better solution the Greedy heuristic can provide. Thus the Distance Matrix Method can be used to improve the Greedy heuristic’s performance. Based on this observation, a method called Minimizing the Variance of Distance Matrix (MVODM) is proposed. This method can effectively improve the Greedy heuristic when applied. In order to further improve the efficiency, a heuristic that can quickly provide approximate solutions of the MVODM is developed. Finally, an algorithm combining this approximate MVODM method and Greedy heuristic is developed. Extensive computational experiments on a well-established test suite consisting of 82 benchmark instances with city numbers ranging from 1000 to 10,000,000 demonstrate that this algorithm not only improves the average tour quality by 40.1%, but also reduces the running time by 21.7%, comparing with the Greedy algorithm. More importantly, the performance of the proposed approach can beat the Savings heuristic, the best known construction heuristic in the TSP literature.