This paper presents a hybrid self-adaptive global best harmony search algorithm (HSGHSA) to improve the performance of harmony search algorithm (HSA) for solving vehicle routing problems with time windows (VRPTW). To explore the search space more efficiently, the proposed HSGHSA couples an improved variant of HSA called global best harmony search algorithm with a self-adaptive mechanism for tuning its control parameters. Moreover, the HSGHSA adopts six local search (LS) neighborhood structures to enhance its exploitation capability. The effectiveness of HSGHSA is evaluated against Solomon’s VRPTW benchmark and its performance is compared with HSA and several state-of-the-art algorithms. The obtained results confirm that the HSGHSA produces very competitive results compared to the other algorithms.