The ability to understand natural-language instructions is crit- ical to building intelligent agents that interact with humans. We present a system that learns to transform natural-language navigation instructions into executable formal plans. Given no prior linguistic knowledge, the system learns by simply observing how humans follow navigation instructions. The system is evaluated in three complex virtual indoor environ- ments with numerous objects and landmarks. A previously collected realistic corpus of complex English navigation in- structions for these environments is used for training and test- ing data. By using a learned lexicon to refine inferred plans and a supervised learner to induce a semantic parser, the sys- tem is able to automatically learn to correctly interpret a rea- sonable fraction of the complex instructions in this corpus.