Predicting the tertiary structure of proteins from their linear sequence is a big challenge in biology. The existing computational methods are not powerful enough to search for the precise structure in a huge conformational space. This inadequate capability of the computational methods, however, is a major obstacle when trying to tackle this problem. The observations of some previous studies have revealed much interest in hybridizing a local search-based metahuristic algorithm within the population-based metahuristic algorithm. This study introduces a hybrid harmony search algorithm (HHSA) as a means to solve ab initio protein tertiary structure prediction problem. In HHSA, the iterated local search (ILS) is incorporated with the harmony search algorithm (HSA) to empower it so as to find the local optimal solution within the search space of the new harmony. Furthermore, the global-best concept of particle swarm optimization (PSO) is incorporated in memory consideration as a selection scheme to accelerate the convergence speed. The HHSA predicts the tertiary structure of a protein giving its sequence alone (i. e., from scratch). Our algorithm converges faster than the classical harmony search algorithm. We evaluate our algorithm using two protein sequences. The results show that our algorithm can find more precise solutions than other previous studies. © 2012 Springer-Verlag.