Location-based queries (LBQ) are becoming more and more useful in location-based services (LBSs) such as those provided through mobile phones, personal digital assistants (PDAs), and laptops. They are context aware since they support the access to information by taking into account the spatial context of the user when submitting the query, and the spatial location of the searched information (instances). Generally, the key-selection condition is a constraint on the distance of the instances from the user location. One deficiency of current approaches in evaluating LBQs is the fact that they do not manage the uncertainty that often characterizes the knowledge of either the user position or the searched instances or both of them, thus they do not produce query answers with estimates of their possible validity. In the paper, after analyzing the processes involved in a LBS that may generate uncertainty, a model for representing and evaluating LBQs affected by uncertainty is proposed, in which uncertainty and imprecision can affect both location information and the spatial condition, i.e., the query scope. Distinct situations of uncertainty in LBQs are analyzed and for each of them a two-step evaluation procedure is proposed based on a fixed-cost filter phase and on a refinement phase that produces ranked results reflecting an estimate of their validity.