Modern software systems, such as Cyber-Physical Systems (CPSs), often require interacting with environment or human. As environment and human are unpredictable or non-determinate, uncertainty is inevitable in such systems. In this paper, we proposed UncerTest to test such systems (i.e., CPSs in our context) with an explicit consideration of uncertainty, through test design, test generation, test optimization and test reporting. UncerTest is a model-based and search-based approach that rely on belief models — a test ready model with explicit subjective uncertainties. In UncerTest, we extended an uncertainty-wise test modeling framework (UncerTum) for designing and enabling of introduction of indeterminacy sources in the environment during test execution. To obtain tests, we first proposed an uncertainty-wise test generation with two strategies, designed for different coverage criteria of models, for enabling an automated test generations with uncertainties. In addition, we developed an uncertainty-wise test minimization to optimize the generated tests based on uncertainty related property using multi-objective search. We conducted an extensive empirical study with two phases to evaluate UncerTest with five use cases of two industrial CPS case studies. In the first phase, eight commonly used multi-objective search algorithms were selected for studying the best algorithm for each of the four minimization strategies. Next, the test cases obtained with UncerTest strategies (i.e., two generation strategies combined with four minimization strategies with the best algorithm) were executed on the two real CPSs for studying the performance of each UncerTest strategies. With the best strategy, we managed to observe 51% more uncertainties due to unknown indeterminate behaviors of the physical environments of the CPSs as compared to the other test strategies. In addition, with the same strategy, we managed to observe 118% more unknown uncertainties that are not specified in the test ready models.