Krill herd (KH) is a stochastic nature-inspired algorithm, it has been successfully used to solve many complex optimization problems. The performance of krill herd algorithm (KHA) is efiected by poor ex-ploitation capability. This paper proposes new data clustering algorithm based on a hybrid of krill herd algorithm (KHA) and harmony search (HS) algorithm (Harmony-KHA) in order to improve the data clustering technique. This hybrid strategy seeking to enhance the global search ca-pability of the KHA. The enhancement includes of adding global search operator from HS algorithm for exploration around the optimal solution in KH and thus kill individuals move towards the global best solution. The proposed method is applied to preserve the best krill individual during the krill position update. Experiments were conducted using four standard datasets from the UCI Machine Learning Repository, which is used in the domain of data clustering. The results showed that the pro-posed hybrid KHA and HS algorithm (Harmony-KHA) is produced very accurate clusters, especially in the large dataset.