System testing of software applications with a graphical-user interface (GUI) front-end requires that sequences of GUI events, that sample the application’s input space, be generated and executed as test cases on the GUI. However, the context-sensitive behavior of the GUI of most of today’s non-trivial software applications makes it practically impossible to fully determine the software’s input space. Consequently, GUI testers—both automated and manual—working with undetermined input spaces are, in some sense, blindly navigating the GUI, unknowingly missing allowable event sequences, and failing to realize that the GUI implementation may allow the execution of some disallowed sequences. In this paper, we develop a new paradigm for GUI testing, one that we call Observe-Model-Exercise* (OME*) to tackle the challenges of testing context-sensitive GUIs with undetermined input spaces. Starting with an incomplete model of the GUI’s input space, a set of coverage elements to test, and test cases, OME* iteratively observes the existence of new events during execution of the test cases, expands the model of the GUI’s input space, computes new coverage elements, and obtains new test cases to exercise the new elements. Our experiment with 8 open-source software subjects, more than 500,000 test cases running for almost 1,100 machine-days, shows that OME* is able to expand the test space on average by 464.11 percent; it detected 34 faults that had never been detected before.