A multi-gait approach is proposed in this paper for autonomous humanoid robot navigation and obstacle avoidance in unknown complex cluttered environments. The proposed approach is based on an environment-dependent adaptive switching between multiple gait strategies including, in particular, a new low-profile crawling gait that enables humanoid motion in tight vertically constrained spaces in addition to forward walking and side-stepping gaits. The path planning and obstacle avoidance system is based on the GODZILA algorithm that provides a computationally lightweight approach for navigation in unknown environments without requiring building of an environment map. The new low-profile crawling gait is laterally symmetric and utilizes a cooperative motion of both the hands and feet. The addition of this gait expands the set of environments that can be handled by the humanoid robot. The efficacy of the proposed approach is demonstrated through simulations and experimental studies on a NAO humanoid robot.