This paper introduces a novel automatic gait synthesis approach for Humanoid Robots (HRs) by Dynamic Fuzzy Q-Learning (DFQL). The DFQL method is capable of tuning Fuzzy Inference Systems (FISs) online. A salient feature of the proposed approach 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 ankles 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 becomes very close to the ideal case. Comparison studies between the DFQL method and conventional FQL approaches demonstrate that the DFQL method is superior.