Fuzzy C-Means clustering is among the most successful clustering techniques available in the literature. The capacitated vehicle routing problem (CVRP) is one of the most studied NP-hard problems. CVRP has attracted the attention of many researchers due to its importance within the supply chain management field. This study aims to develop a fuzzy c-means clustering heuristic to efficiently solve the CVRP with large numbers of customers by using cluster-first route-second method (CFRS). CFRS is a two-phase technique, where in the first phase customers are grouped into, and in the second phase each cluster is solved independently as a traveling salesman problem (TSP). This work is concerned the clustering phase of the CFRS. The second phase of the CFRS method is solved using traditional optimization software. A modified demand weighted fuzzy c-means clustering algorithm is developed to solve the clustering phase. Twentyfive instances are solved to evaluate the efficiency of the proposed algorithm. Some of them are large instances with more than 500 customers. Promising results in terms of accuracy and processing time are obtained.