Abstract: In this paper, a dynamic (i.e. self-adaptive according to the number of nodes) Simulated Annealing Algorithm is presented to solve the well-known Traveling Salesman Problem (TSP). In the presented algorithm, the temperature parameter is adjusted on the basis of the number of nodes. To achieve dynamicity, a new parameter named “Cooling Enhancer” is introduced to control the cooling rate, thereby, regulating the temperature. Additionally, an enhanced version of acceptance probability has been used. The efficacy of Dynamic Simulated Annealing with Cooling Enhancer & Modified Acceptance Probability (DSA-CE&MAP) is compared against the basic simulated annealing algorithm (SA) [2] for some benchmark TSPLIB instances [1]. Experimental results illustrate that the new dynamic simulated annealing algorithm performs better than the basic simulated annealing algorithm for solving TSP. It has been observed that the quality of solutions (i.e. minimum total cost or distance) is significantly increased as compared to earlier method.