We present Impossible Staircase, a real-walking virtual reality system that allows users to climb an infinite virtual tower. Our set-up consists of an one-level scaffold and a lifter. A user climbs up the scaffold by real walking on a stairway while wearing a head-mounted display, and gets reset to the ground level by a lifter imperceptibly. By repeating this process, the user perceives an illusion of climbing an infinite number of levels. Our system achieves the illusion by (1) controlling the movement of the lifter to generate reverse and imperceptible motion, (2) guiding the user through the scaffold with delay mechanisms to reset the lifter in time, and (3) procedural generating overlapping structures to enlarge perceived height of each level. We built a working system and demonstrated it with a 15-min experience. With the working system, we conducted user studies to gain deeper insights into vertical motion simulation and vertical real walking in virtual reality.