Traveling Salesman Problem (TSP) is a significant combinatorial optimization problem. TSP is NP-hard problem which involves finding the minimum tour length among a given set of nodes and return to the starting node knowing that each node must be visited once. This paper proposes a solution to TSP using Firefly Algorithm (FA) and k-means clustering. The proposed approach comprises three major steps: cluster the nodes, find the optimal path in each cluster, and reconnect the clusters. The first step uses k-means clustering to divide the nodes into sub-problems, the second step utilizes FA to find the optimal path in each cluster, finally reconnect all clusters and return the path between them. The experimental results show that the proposed approach provides better results when compared to other algorithms from the literature.