In this paper we propose a new method for generating test scenarios for black-box autonomous systems that demonstrate critical transitions in performance modes. This method provides a test engineer with key insights into the software’s decision-making engine and how those decisions affect transitions between performance modes. We achieve this via adaptive, simulation-based testing of the autonomous system where each sample represents a simulated scenario. The test scenario, i.e the system input, represents a given configuration of environmental or mission parameters and the resulting outputs are the system’s performance based on high-level success criteria. For realistic testing scenarios, the dimensionality of the configuration space and the computational expense of high-fidelity simulations precludes exhaustive or uniform sampling. Thus, we have developed specialized adaptive search algorithms designed to discover performance boundaries of the autonomy using a minimal number of samples. Further, unsupervised clustering techniques are presented that can group test scenarios by the resulting performance modes and sort them by those which are most effective at diagnosing changes in the autonomous system’s behavior. The result is a testing framework that gives the test engineer a set of diverse scenarios that exercises the decision boundaries of the autonomous system under test.