Uncertainty and fuzziness are semantically different in spatio-temporal data management and related applications. We propose a novel type of query, namely fuzzy spatio-temporal range (FSTR) query over uncertain moving objects, which simultaneously integrates the location uncertainty and the users’ preferences expressed qualitatively with fuzzy conditions or items. Both the temporal and spatial searching conditions in FSTR queries are vague, namely they have no crisp boundaries. FSTR queries are executed on the uncertain datasets. To address these two kinds of indeterminate phenomena, we utilize fuzzy sets and probability density functions (pdfs) to represent fuzzy querying conditions and the possible distributions of objects’ locations respectively. We present the qualifying guarantee evaluation of objects about vague query conditions, and propose pruning techniques based on the α-cut of fuzzy set to shrink the search space efficiently. We also design rules to reject non-qualifying objects and validate qualifying objects in order to avoid unnecessary costly numeric integrations in the refinement step. The approach here makes no assumption on objects’ pdfs and is applicable to arbitrary kind of pdfs. FSTR queries can be taken as the general form of existing certain or uncertain range queries. An empirical study has been conducted to demonstrate the efficiency and effectiveness of algorithms under various experimental settings. The experiment results show that about 30%~90% objects in the query results are obtained by the proposed rules directly without costly matching degree evaluation.