In this paper, a new gait research for humanoid robot is presented. By computing the trajectory of center of mass (CoM) for humanoid robot, trajectory of hip joint and ankle joint are developed based on 3D inverted pendulum model. The actual location of the waist position obtained by multi-link model through the center of mass for humanoid robot is in coordinate of the waist of humanoid robot. Trajectory of hip joint and ankle joint are calculated. This paper presents a gait generation method with curve fitting. Using genetic algorithm, humanoid robot can autonomously search for a good gait trajectory. The experimental results show that gait trajectory for humanoid robot can be generated by applying to genetic algorithm. Our proposed method is verified satisfactorily.