Polyphase codes are widely used in radar systems as a pulse compression approach due to the fact that they produce lower side-lobes in the compressed signal than other methods. Unfortunately, the efficient design of such codes comprises by itself a non-linear n-dimensional NP-hard optimization problem, which has been so far tackled by using evolutionary techniques. In this paper we present a novel heuristic approach consisting of a Harmony Search algorithm hybridized with both a dynamic-step gradient-guided and a random walk local search procedures. The second procedure is applied when the gradient of the underlying fitness function is zero, i.e. when facing a flat region during the search process over the solution space. A simulation-based comparison study with the best results found in the literature is presented, from where it is concluded that our proposed algorithm outperforms other existing approaches in the literature for n=1,...,15.