In this paper a novel multilevel thresholding algorithm using a meta-heuristic Krill Herd Optimization (KHO) algorithm has been proposed for solving the image segmentation problem. The optimum threshold values are determined by the maximization of Kapur’s or Otsu’s objective function using Krill Herd Optimization technique. The proposed method reduces the computational time for computing the optimum thresholds for multilevel thresholding. The applicability and computational efficiency of the Krill Herd Optimization based multilevel thresholding is demonstrated using various benchmark images. A detailed comparative analysis with other existing bio-inspired techniques based multilevel thresholding techniques such as Bacterial Foraging (BF), Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Moth-Flame Optimization (MFO) has been performed to prove the superior performance of the proposed method.