In this paper, a dependable humanoid navigation system is proposed by considering many difficulties in humanoid navigation based on bipedal locomotion in an uncertain environment. In particular, we propose a layered architecture to resolve complicated problems through a hierarchical manner. Within the proposed software architecture, a walking path planner, a walking footstep planner, and a walking pattern generator are integrated in a hierarchy to create a reliable motion that overcomes foot slippage and localization sensor noise. Each layer is designed to overcome difficulties originating from bipedal locomotion such as unstable dynamics, inclusion of a sinusoidal noise component in the localization sensor measurement, and disturbance regarding discrete footstepping. The designed navigation system is implemented on a human-sized experimental humanoid platform and is tested for the evaluation of its reliability and robustness in various tasks.