In this paper, a new crossover operator named Neighbor-based Constructive Crossover (NCX) is evolved for a genetic algorithm that generates high quality solutions to the Traveling Salesman Problem (TSP). The proposed crossover operator uses the better edges present in parents’ structure by comparing the neighboring nodes of a node in order to generate off-springs. The efficacy of the proposed crossover operator, NCX is set against two other crossover operators, single point crossover (SPCX) [19] and sequential constructive crossover (SCX) [1] for several standard TSPLIB instances [2]. Empirical results and observations illustrate that the new crossover operator is better than the SPCX and SCX in terms of quality of solutions.