In this paper, an evolutionary optimized footstep planner for the navigation of humanoid robots is proposed. A footstep planner based on a univector field navigation method is proposed to generate a command state (CS) as an input to a modifiable walking pattern generator (MWPG) at each footstep. The MWPG generates associated trajectories of every leg joint to follow the given CS. In order to satisfy various objectives in the navigation, the univector fields are optimized by evolutionary programming. The three objectives, shortest elapsed time to get to a destination, safety without obstacle collision, and less energy consumption, are considered with mechanical constraints of a real humanoid robot, that is, the maximum step length and allowable yawing range of the feet. The effectiveness of the proposed algorithm is demonstrated through both computer simulation and experiment for a small-sized humanoid robot, HanSaRam-IX.