This paper introduces a novel automatic gait syn-thesis approach for Humanoid Robots (HRs) by Dy-namic Fuzzy Q-Learning (DFQL). The DFQL meth-od is capable of tuning Fuzzy Inference Systems (FISs) online. A salient feature of the proposed ap-proach is that the DFQL controller can automatically generate fuzzy rules without a priori knowledge and it is capable of dealing with highly complex dynamic systems. The challenge for automatic gait synthesis of an HR is to define gait trajectories for hips and an-kles so that motions of other joints can be regulate simultaneously. Because stability is one of the most common concerns for HRs, a self-learning control strategy of improving dynamic stability based on the Zero Moment Point (ZMP) criterion is developed. A Dynamic Fuzzy Q-Learning (DFQL) controller is proposed to automatically generate the hip motion trajectory, as hip motion plays the most important role in dynamic stability. Simulation results show that the DFQL controller is capable of improving dynamic stability as the actual ZMP trajectory be-comes very close to the ideal case. Comparison stud-ies between the DFQL method and conventional FQL approaches demonstrate that the DFQL method is superior.