Harmony search (HS), inspired by the music improvisation process, is a new meta-heuristic optimization method and has been used to tackle various optimization problems in discrete and continuous space successfully. However, the standard HS algorithm is not suitable for settling discrete binary problems. To extend HS to solve the binary-coded problems effectively, a novel discrete binary harmony search (DBHS) algorithm is proposed in this paper. A new pitch adjustment rule is developed to enhance the optimization ability of DBHS. Then parameter studies are performed to investigate the properties of DBHS, and the recommended parameter values are given. The results of numerical experiments demonstrate that the proposed DBHS is valid and outperforms the discrete binary particle swarm optimization algorithm and the standard HS.