A novel bio-inspired optimization algorithm called elephant search algorithm (ESA) has been applied to solve NP-hard problems including the classical traveling salesman problem (TS) in this paper. ESA emerges from the hybridization of evolutionary mechanism and dual balancing of exploitation and exploration. The design of ESA is inspired by the behavioral characteristics of elephant herds; hence, the name Elephant Search Algorithm which divides the search agents into two groups representing the dual search patterns. The male elephants are search agents that outreach to different dimensions of search space afar; the female elephants form groups of search agents doing local search at certain close proximities. By computer simulation, ESA is shown to outperform other metaheuristic algorithms over the popular benchmarking optimization functions which are NP-hard in nature. In terms of fitness values in optimization, ESA is ranked after Firefly algorithm showing superior performance over the other ones. The performance of ESA is most stable when compared to all other metaheuristic algorithms. When ESA is applied to the traveling salesman problem, different ratios of gender groups yield different results. Overall, ESA is shown to be capable of providing approximate solutions in TSP.