This paper proposes a novel online multiobjective evolutionary approach for the navigation of humanoid robots. In the proposed approach, the humanoid robot navigation problem is decomposed into a series of small multiobjective optimization problems (MOPs) with corresponding local information. Using multiobjective evolutionary algorithms (MOEAs), the MOPs can be successively solved while the robot is walking. In addition, to achieve significant reductions in the processing time of the MOEAs for online implementation while maintaining robustness and scalability, a novel homogeneous parallel computing method is devised for the MOEAs. Multiobjective particle swarm optimization with preference-based sort (MOPSO-PS) is employed as the MOEA to reflect the user-defined preference for each objective during navigation. The effectiveness of the proposed online approach is demonstrated through well-known benchmark problems and a robot simulator. In both the simulation and the experiment, a humanoid robot successfully navigates to the goal, satisfying the preferences for various objectives, with local information in an environment without a global map.