Moth-flame optimizer (MFO) is one of the recently proposed metaheuristic optimization techniques which has been successfully used in wide range of applications. However, there are two issues with the MFO algorithm. First, as a stochastic technique, MFO may prematurely converge at some local minima during the search process. Second, the original MFO was developed for continuous search space problems and is not directly applicable to, e.g., permutation-based problems (PBP). In this paper, a novel perturbation strategy is introduced to the MFO algorithm to avoid probable local minima regions. This strategy works as follows: if the best solution obtained so far doesn’t improve for a given number of consecutive iterations, the current population of solutions is perturbed using some crossover mechanism as an attempt to explore new promising neighbourhoods in the search space. In addition, smallest position values mapping technique is employed in order for the proposed, termed CrossMFO (COMFO), algorithm to be applicable to PBP problems. It is noticed that, despite these modifications, the proposed COMFO has the same time complexity order as the original MFO. Extensive simulation experiments are conducted to compare the proposed COMFO to the MFO, other enhanced versions of MFO, and some metaheuristic optimizers in solving the well-known Travelling Salesman Problem (TSP). Empirical results show that the solutions obtained using MFO are improved by a factor of 24–47% on average for large TSP instances having more than 100 cities using COMFO and can even reach 38–58% using different settings. In addition, compared to other algorithms in the literature, the proposed algorithm provides, on average, better solutions. Hence, it can be considered a promising and efficient technique for this type of problems.