With the growing nature of data in the daily business environment, the analysis and implementation of data seems to be very important in success of business. Data mining is a useful and efficient process of analyzing such data and clustering is a popular data analysis and data mining technique. K-means is the most popular clustering algorithm due to its simplicity and high speed in clustering large datasets. However, K-means has two drawbacks. It is sensitive to initial states and convergence to local optima in some complicated cases. In order to overcome these drawbacks, lots of studies have been done in clustering. This paper presents an efficient hybrid clustering algorithm based on combining Modified Grenade Explosion Method and K-means. We compared proposed algorithm with other heuristics algorithms in clustering, such as traditional K-means, genetic K-means algorithm, GA-PSO and Imperialist Competitive Algorithm by applying them on several well-known datasets. The simulation results show that the proposed evolutionary optimization algorithm is robustness and efficient enough to use in data clustering.