In this paper, a humanoid robot is simulated and implemented to walk up a staircase using the blending polynomial and genetic algorithm. Using recently developed kinematics for a biped robot, four schemes for walking up a staircase are newly proposed and simulated separately. For the two schemes of landing a swaying leg on the upper stair, the joint trajectories of seven motors are particularly optimized to generate an energy-minimal motion with the guarantee of walking stability. The proposed scheme of walking upstair is validated by an experiment with a small humanoid robot.